CIRCT  20.0.0git
SCFToCalyx.cpp
Go to the documentation of this file.
1 //===- SCFToCalyx.cpp - SCF to Calyx pass entry point -----------*- 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 // This is the main SCF to Calyx conversion pass implementation.
10 //
11 //===----------------------------------------------------------------------===//
12 
18 #include "circt/Dialect/HW/HWOps.h"
19 #include "mlir/Conversion/LLVMCommon/ConversionTarget.h"
20 #include "mlir/Conversion/LLVMCommon/Pattern.h"
21 #include "mlir/Dialect/Arith/IR/Arith.h"
22 #include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
23 #include "mlir/Dialect/Func/IR/FuncOps.h"
24 #include "mlir/Dialect/MemRef/IR/MemRef.h"
25 #include "mlir/Dialect/SCF/IR/SCF.h"
26 #include "mlir/IR/AsmState.h"
27 #include "mlir/IR/Matchers.h"
28 #include "mlir/Pass/Pass.h"
29 #include "mlir/Support/LogicalResult.h"
30 #include "mlir/Transforms/GreedyPatternRewriteDriver.h"
31 #include "llvm/ADT/TypeSwitch.h"
32 #include "llvm/Support/LogicalResult.h"
33 
34 #include <variant>
35 
36 namespace circt {
37 #define GEN_PASS_DEF_SCFTOCALYX
38 #include "circt/Conversion/Passes.h.inc"
39 } // namespace circt
40 
41 using namespace llvm;
42 using namespace mlir;
43 using namespace mlir::arith;
44 using namespace mlir::cf;
45 using namespace mlir::func;
46 namespace circt {
47 class ComponentLoweringStateInterface;
48 namespace scftocalyx {
49 
50 //===----------------------------------------------------------------------===//
51 // Utility types
52 //===----------------------------------------------------------------------===//
53 
54 class ScfWhileOp : public calyx::WhileOpInterface<scf::WhileOp> {
55 public:
56  explicit ScfWhileOp(scf::WhileOp op)
57  : calyx::WhileOpInterface<scf::WhileOp>(op) {}
58 
59  Block::BlockArgListType getBodyArgs() override {
60  return getOperation().getAfterArguments();
61  }
62 
63  Block *getBodyBlock() override { return &getOperation().getAfter().front(); }
64 
65  Block *getConditionBlock() override {
66  return &getOperation().getBefore().front();
67  }
68 
69  Value getConditionValue() override {
70  return getOperation().getConditionOp().getOperand(0);
71  }
72 
73  std::optional<int64_t> getBound() override { return std::nullopt; }
74 };
75 
76 class ScfForOp : public calyx::RepeatOpInterface<scf::ForOp> {
77 public:
78  explicit ScfForOp(scf::ForOp op) : calyx::RepeatOpInterface<scf::ForOp>(op) {}
79 
80  Block::BlockArgListType getBodyArgs() override {
81  return getOperation().getRegion().getArguments();
82  }
83 
84  Block *getBodyBlock() override {
85  return &getOperation().getRegion().getBlocks().front();
86  }
87 
88  std::optional<int64_t> getBound() override {
89  return constantTripCount(getOperation().getLowerBound(),
90  getOperation().getUpperBound(),
91  getOperation().getStep());
92  }
93 };
94 
95 //===----------------------------------------------------------------------===//
96 // Lowering state classes
97 //===----------------------------------------------------------------------===//
98 
100  scf::IfOp ifOp;
101 };
102 
104  /// While operation to schedule.
106 };
107 
109  /// For operation to schedule.
111  /// Bound
112  uint64_t bound;
113 };
114 
116  /// Instance for invoking.
117  calyx::InstanceOp instanceOp;
118  // CallOp for getting the arguments.
119  func::CallOp callOp;
120 };
121 
123  /// Parallel operation to schedule.
124  scf::ParallelOp parOp;
125 };
126 
127 /// A variant of types representing scheduleable operations.
129  std::variant<calyx::GroupOp, WhileScheduleable, ForScheduleable,
131 
133 public:
134  void setThenGroup(scf::IfOp op, calyx::GroupOp group) {
135  Operation *operation = op.getOperation();
136  assert(thenGroup.count(operation) == 0 &&
137  "A then group was already set for this scf::IfOp!\n");
138  thenGroup[operation] = group;
139  }
140 
141  calyx::GroupOp getThenGroup(scf::IfOp op) {
142  auto it = thenGroup.find(op.getOperation());
143  assert(it != thenGroup.end() &&
144  "No then group was set for this scf::IfOp!\n");
145  return it->second;
146  }
147 
148  void setElseGroup(scf::IfOp op, calyx::GroupOp group) {
149  Operation *operation = op.getOperation();
150  assert(elseGroup.count(operation) == 0 &&
151  "An else group was already set for this scf::IfOp!\n");
152  elseGroup[operation] = group;
153  }
154 
155  calyx::GroupOp getElseGroup(scf::IfOp op) {
156  auto it = elseGroup.find(op.getOperation());
157  assert(it != elseGroup.end() &&
158  "No else group was set for this scf::IfOp!\n");
159  return it->second;
160  }
161 
162  void setResultRegs(scf::IfOp op, calyx::RegisterOp reg, unsigned idx) {
163  assert(resultRegs[op.getOperation()].count(idx) == 0 &&
164  "A register was already registered for the given yield result.\n");
165  assert(idx < op->getNumOperands());
166  resultRegs[op.getOperation()][idx] = reg;
167  }
168 
169  const DenseMap<unsigned, calyx::RegisterOp> &getResultRegs(scf::IfOp op) {
170  return resultRegs[op.getOperation()];
171  }
172 
173  calyx::RegisterOp getResultRegs(scf::IfOp op, unsigned idx) {
174  auto regs = getResultRegs(op);
175  auto it = regs.find(idx);
176  assert(it != regs.end() && "resultReg not found");
177  return it->second;
178  }
179 
180 private:
181  DenseMap<Operation *, calyx::GroupOp> thenGroup;
182  DenseMap<Operation *, calyx::GroupOp> elseGroup;
183  DenseMap<Operation *, DenseMap<unsigned, calyx::RegisterOp>> resultRegs;
184 };
185 
187  : calyx::LoopLoweringStateInterface<ScfWhileOp> {
188 public:
189  SmallVector<calyx::GroupOp> getWhileLoopInitGroups(ScfWhileOp op) {
190  return getLoopInitGroups(std::move(op));
191  }
193  OpBuilder &builder, ScfWhileOp op, calyx::ComponentOp componentOp,
194  Twine uniqueSuffix, MutableArrayRef<OpOperand> ops) {
195  return buildLoopIterArgAssignments(builder, std::move(op), componentOp,
196  uniqueSuffix, ops);
197  }
198  void addWhileLoopIterReg(ScfWhileOp op, calyx::RegisterOp reg, unsigned idx) {
199  return addLoopIterReg(std::move(op), reg, idx);
200  }
201  const DenseMap<unsigned, calyx::RegisterOp> &
203  return getLoopIterRegs(std::move(op));
204  }
205  void setWhileLoopLatchGroup(ScfWhileOp op, calyx::GroupOp group) {
206  return setLoopLatchGroup(std::move(op), group);
207  }
208  calyx::GroupOp getWhileLoopLatchGroup(ScfWhileOp op) {
209  return getLoopLatchGroup(std::move(op));
210  }
212  SmallVector<calyx::GroupOp> groups) {
213  return setLoopInitGroups(std::move(op), std::move(groups));
214  }
215 };
216 
219 public:
220  SmallVector<calyx::GroupOp> getForLoopInitGroups(ScfForOp op) {
221  return getLoopInitGroups(std::move(op));
222  }
224  OpBuilder &builder, ScfForOp op, calyx::ComponentOp componentOp,
225  Twine uniqueSuffix, MutableArrayRef<OpOperand> ops) {
226  return buildLoopIterArgAssignments(builder, std::move(op), componentOp,
227  uniqueSuffix, ops);
228  }
229  void addForLoopIterReg(ScfForOp op, calyx::RegisterOp reg, unsigned idx) {
230  return addLoopIterReg(std::move(op), reg, idx);
231  }
232  const DenseMap<unsigned, calyx::RegisterOp> &getForLoopIterRegs(ScfForOp op) {
233  return getLoopIterRegs(std::move(op));
234  }
235  calyx::RegisterOp getForLoopIterReg(ScfForOp op, unsigned idx) {
236  return getLoopIterReg(std::move(op), idx);
237  }
238  void setForLoopLatchGroup(ScfForOp op, calyx::GroupOp group) {
239  return setLoopLatchGroup(std::move(op), group);
240  }
241  calyx::GroupOp getForLoopLatchGroup(ScfForOp op) {
242  return getLoopLatchGroup(std::move(op));
243  }
244  void setForLoopInitGroups(ScfForOp op, SmallVector<calyx::GroupOp> groups) {
245  return setLoopInitGroups(std::move(op), std::move(groups));
246  }
247 };
248 
249 /// Handles the current state of lowering of a Calyx component. It is mainly
250 /// used as a key/value store for recording information during partial lowering,
251 /// which is required at later lowering passes.
256  public calyx::SchedulerInterface<Scheduleable> {
257 public:
258  ComponentLoweringState(calyx::ComponentOp component)
259  : calyx::ComponentLoweringStateInterface(component) {}
260 };
261 
262 //===----------------------------------------------------------------------===//
263 // Conversion patterns
264 //===----------------------------------------------------------------------===//
265 
266 /// Iterate through the operations of a source function and instantiate
267 /// components or primitives based on the type of the operations.
269  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
270 
271  LogicalResult
273  PatternRewriter &rewriter) const override {
274  /// We walk the operations of the funcOp to ensure that all def's have
275  /// been visited before their uses.
276  bool opBuiltSuccessfully = true;
277  funcOp.walk([&](Operation *_op) {
278  opBuiltSuccessfully &=
279  TypeSwitch<mlir::Operation *, bool>(_op)
280  .template Case<arith::ConstantOp, ReturnOp, BranchOpInterface,
281  /// SCF
282  scf::YieldOp, scf::WhileOp, scf::ForOp, scf::IfOp,
283  scf::ParallelOp, scf::ReduceOp,
284  /// memref
285  memref::AllocOp, memref::AllocaOp, memref::LoadOp,
286  memref::StoreOp,
287  /// standard arithmetic
288  AddIOp, SubIOp, CmpIOp, ShLIOp, ShRUIOp, ShRSIOp,
289  AndIOp, XOrIOp, OrIOp, ExtUIOp, ExtSIOp, TruncIOp,
290  MulIOp, DivUIOp, DivSIOp, RemUIOp, RemSIOp,
291  /// floating point
292  AddFOp, MulFOp, CmpFOp,
293  /// others
294  SelectOp, IndexCastOp, CallOp>(
295  [&](auto op) { return buildOp(rewriter, op).succeeded(); })
296  .template Case<FuncOp, scf::ConditionOp>([&](auto) {
297  /// Skip: these special cases will be handled separately.
298  return true;
299  })
300  .Default([&](auto op) {
301  op->emitError() << "Unhandled operation during BuildOpGroups()";
302  return false;
303  });
304 
305  return opBuiltSuccessfully ? WalkResult::advance()
306  : WalkResult::interrupt();
307  });
308 
309  return success(opBuiltSuccessfully);
310  }
311 
312 private:
313  /// Op builder specializations.
314  LogicalResult buildOp(PatternRewriter &rewriter, scf::YieldOp yieldOp) const;
315  LogicalResult buildOp(PatternRewriter &rewriter,
316  BranchOpInterface brOp) const;
317  LogicalResult buildOp(PatternRewriter &rewriter,
318  arith::ConstantOp constOp) const;
319  LogicalResult buildOp(PatternRewriter &rewriter, SelectOp op) const;
320  LogicalResult buildOp(PatternRewriter &rewriter, AddIOp op) const;
321  LogicalResult buildOp(PatternRewriter &rewriter, SubIOp op) const;
322  LogicalResult buildOp(PatternRewriter &rewriter, MulIOp op) const;
323  LogicalResult buildOp(PatternRewriter &rewriter, DivUIOp op) const;
324  LogicalResult buildOp(PatternRewriter &rewriter, DivSIOp op) const;
325  LogicalResult buildOp(PatternRewriter &rewriter, RemUIOp op) const;
326  LogicalResult buildOp(PatternRewriter &rewriter, RemSIOp op) const;
327  LogicalResult buildOp(PatternRewriter &rewriter, AddFOp op) const;
328  LogicalResult buildOp(PatternRewriter &rewriter, MulFOp op) const;
329  LogicalResult buildOp(PatternRewriter &rewriter, CmpFOp op) const;
330  LogicalResult buildOp(PatternRewriter &rewriter, ShRUIOp op) const;
331  LogicalResult buildOp(PatternRewriter &rewriter, ShRSIOp op) const;
332  LogicalResult buildOp(PatternRewriter &rewriter, ShLIOp op) const;
333  LogicalResult buildOp(PatternRewriter &rewriter, AndIOp op) const;
334  LogicalResult buildOp(PatternRewriter &rewriter, OrIOp op) const;
335  LogicalResult buildOp(PatternRewriter &rewriter, XOrIOp op) const;
336  LogicalResult buildOp(PatternRewriter &rewriter, CmpIOp op) const;
337  LogicalResult buildOp(PatternRewriter &rewriter, TruncIOp op) const;
338  LogicalResult buildOp(PatternRewriter &rewriter, ExtUIOp op) const;
339  LogicalResult buildOp(PatternRewriter &rewriter, ExtSIOp op) const;
340  LogicalResult buildOp(PatternRewriter &rewriter, ReturnOp op) const;
341  LogicalResult buildOp(PatternRewriter &rewriter, IndexCastOp op) const;
342  LogicalResult buildOp(PatternRewriter &rewriter, memref::AllocOp op) const;
343  LogicalResult buildOp(PatternRewriter &rewriter, memref::AllocaOp op) const;
344  LogicalResult buildOp(PatternRewriter &rewriter, memref::LoadOp op) const;
345  LogicalResult buildOp(PatternRewriter &rewriter, memref::StoreOp op) const;
346  LogicalResult buildOp(PatternRewriter &rewriter, scf::WhileOp whileOp) const;
347  LogicalResult buildOp(PatternRewriter &rewriter, scf::ForOp forOp) const;
348  LogicalResult buildOp(PatternRewriter &rewriter, scf::IfOp ifOp) const;
349  LogicalResult buildOp(PatternRewriter &rewriter,
350  scf::ReduceOp reduceOp) const;
351  LogicalResult buildOp(PatternRewriter &rewriter,
352  scf::ParallelOp parallelOp) const;
353  LogicalResult buildOp(PatternRewriter &rewriter, CallOp callOp) const;
354 
355  /// buildLibraryOp will build a TCalyxLibOp inside a TGroupOp based on the
356  /// source operation TSrcOp.
357  template <typename TGroupOp, typename TCalyxLibOp, typename TSrcOp>
358  LogicalResult buildLibraryOp(PatternRewriter &rewriter, TSrcOp op,
359  TypeRange srcTypes, TypeRange dstTypes) const {
360  SmallVector<Type> types;
361  llvm::append_range(types, srcTypes);
362  llvm::append_range(types, dstTypes);
363 
364  auto calyxOp =
365  getState<ComponentLoweringState>().getNewLibraryOpInstance<TCalyxLibOp>(
366  rewriter, op.getLoc(), types);
367 
368  auto directions = calyxOp.portDirections();
369  SmallVector<Value, 4> opInputPorts;
370  SmallVector<Value, 4> opOutputPorts;
371  for (auto dir : enumerate(directions)) {
372  if (dir.value() == calyx::Direction::Input)
373  opInputPorts.push_back(calyxOp.getResult(dir.index()));
374  else
375  opOutputPorts.push_back(calyxOp.getResult(dir.index()));
376  }
377  assert(
378  opInputPorts.size() == op->getNumOperands() &&
379  opOutputPorts.size() == op->getNumResults() &&
380  "Expected an equal number of in/out ports in the Calyx library op with "
381  "respect to the number of operands/results of the source operation.");
382 
383  /// Create assignments to the inputs of the library op.
384  auto group = createGroupForOp<TGroupOp>(rewriter, op);
385  rewriter.setInsertionPointToEnd(group.getBodyBlock());
386  for (auto dstOp : enumerate(opInputPorts))
387  rewriter.create<calyx::AssignOp>(op.getLoc(), dstOp.value(),
388  op->getOperand(dstOp.index()));
389 
390  /// Replace the result values of the source operator with the new operator.
391  for (auto res : enumerate(opOutputPorts)) {
392  getState<ComponentLoweringState>().registerEvaluatingGroup(res.value(),
393  group);
394  op->getResult(res.index()).replaceAllUsesWith(res.value());
395  }
396  return success();
397  }
398 
399  /// buildLibraryOp which provides in- and output types based on the operands
400  /// and results of the op argument.
401  template <typename TGroupOp, typename TCalyxLibOp, typename TSrcOp>
402  LogicalResult buildLibraryOp(PatternRewriter &rewriter, TSrcOp op) const {
403  return buildLibraryOp<TGroupOp, TCalyxLibOp, TSrcOp>(
404  rewriter, op, op.getOperandTypes(), op->getResultTypes());
405  }
406 
407  /// Creates a group named by the basic block which the input op resides in.
408  template <typename TGroupOp>
409  TGroupOp createGroupForOp(PatternRewriter &rewriter, Operation *op) const {
410  Block *block = op->getBlock();
411  auto groupName = getState<ComponentLoweringState>().getUniqueName(
412  loweringState().blockName(block));
413  return calyx::createGroup<TGroupOp>(
414  rewriter, getState<ComponentLoweringState>().getComponentOp(),
415  op->getLoc(), groupName);
416  }
417 
418  /// buildLibraryBinaryPipeOp will build a TCalyxLibBinaryPipeOp, to
419  /// deal with MulIOp, DivUIOp and RemUIOp.
420  template <typename TOpType, typename TSrcOp>
421  LogicalResult buildLibraryBinaryPipeOp(PatternRewriter &rewriter, TSrcOp op,
422  TOpType opPipe, Value out) const {
423  StringRef opName = TSrcOp::getOperationName().split(".").second;
424  Location loc = op.getLoc();
425  Type width = op.getResult().getType();
426  auto reg = createRegister(
427  op.getLoc(), rewriter, getComponent(), width.getIntOrFloatBitWidth(),
428  getState<ComponentLoweringState>().getUniqueName(opName));
429  // Operation pipelines are not combinational, so a GroupOp is required.
430  auto group = createGroupForOp<calyx::GroupOp>(rewriter, op);
431  OpBuilder builder(group->getRegion(0));
432  getState<ComponentLoweringState>().addBlockScheduleable(op->getBlock(),
433  group);
434 
435  rewriter.setInsertionPointToEnd(group.getBodyBlock());
436  rewriter.create<calyx::AssignOp>(loc, opPipe.getLeft(), op.getLhs());
437  rewriter.create<calyx::AssignOp>(loc, opPipe.getRight(), op.getRhs());
438  // Write the output to this register.
439  rewriter.create<calyx::AssignOp>(loc, reg.getIn(), out);
440  // The write enable port is high when the pipeline is done.
441  rewriter.create<calyx::AssignOp>(loc, reg.getWriteEn(), opPipe.getDone());
442  // Set pipelineOp to high as long as its done signal is not high.
443  // This prevents the pipelineOP from executing for the cycle that we write
444  // to register. To get !(pipelineOp.done) we do 1 xor pipelineOp.done
445  hw::ConstantOp c1 = createConstant(loc, rewriter, getComponent(), 1, 1);
446  rewriter.create<calyx::AssignOp>(
447  loc, opPipe.getGo(), c1,
448  comb::createOrFoldNot(group.getLoc(), opPipe.getDone(), builder));
449  // The group is done when the register write is complete.
450  rewriter.create<calyx::GroupDoneOp>(loc, reg.getDone());
451 
452  // Pass the result from the source operation to register holding the resullt
453  // from the Calyx primitive.
454  op.getResult().replaceAllUsesWith(reg.getOut());
455 
456  if (isa<calyx::AddFOpIEEE754>(opPipe)) {
457  auto opFOp = cast<calyx::AddFOpIEEE754>(opPipe);
458  hw::ConstantOp subOp;
459  if (isa<arith::AddFOp>(op)) {
460  subOp = createConstant(loc, rewriter, getComponent(), /*width=*/1,
461  /*subtract=*/0);
462  } else {
463  subOp = createConstant(loc, rewriter, getComponent(), /*width=*/1,
464  /*subtract=*/1);
465  }
466  rewriter.create<calyx::AssignOp>(loc, opFOp.getSubOp(), subOp);
467  }
468 
469  // Register the values for the pipeline.
470  getState<ComponentLoweringState>().registerEvaluatingGroup(out, group);
471  getState<ComponentLoweringState>().registerEvaluatingGroup(opPipe.getLeft(),
472  group);
473  getState<ComponentLoweringState>().registerEvaluatingGroup(
474  opPipe.getRight(), group);
475 
476  return success();
477  }
478 
479  /// Creates assignments within the provided group to the address ports of the
480  /// memoryOp based on the provided addressValues.
481  void assignAddressPorts(PatternRewriter &rewriter, Location loc,
482  calyx::GroupInterface group,
483  calyx::MemoryInterface memoryInterface,
484  Operation::operand_range addressValues) const {
485  IRRewriter::InsertionGuard guard(rewriter);
486  rewriter.setInsertionPointToEnd(group.getBody());
487  auto addrPorts = memoryInterface.addrPorts();
488  if (addressValues.empty()) {
489  assert(
490  addrPorts.size() == 1 &&
491  "We expected a 1 dimensional memory of size 1 because there were no "
492  "address assignment values");
493  // Assign to address 1'd0 in memory.
494  rewriter.create<calyx::AssignOp>(
495  loc, addrPorts[0],
496  createConstant(loc, rewriter, getComponent(), 1, 0));
497  } else {
498  assert(addrPorts.size() == addressValues.size() &&
499  "Mismatch between number of address ports of the provided memory "
500  "and address assignment values");
501  for (auto address : enumerate(addressValues))
502  rewriter.create<calyx::AssignOp>(loc, addrPorts[address.index()],
503  address.value());
504  }
505  }
506 
507  calyx::RegisterOp createSignalRegister(PatternRewriter &rewriter,
508  Value signal, bool invert,
509  StringRef nameSuffix,
510  calyx::CompareFOpIEEE754 calyxCmpFOp,
511  calyx::GroupOp group) const {
512  Location loc = calyxCmpFOp.getLoc();
513  IntegerType one = rewriter.getI1Type();
514  auto component = getComponent();
515  OpBuilder builder(group->getRegion(0));
516  auto reg = createRegister(
517  loc, rewriter, component, 1,
518  getState<ComponentLoweringState>().getUniqueName(nameSuffix));
519  rewriter.create<calyx::AssignOp>(loc, reg.getWriteEn(),
520  calyxCmpFOp.getDone());
521  if (invert) {
522  auto notLibOp = getState<ComponentLoweringState>()
523  .getNewLibraryOpInstance<calyx::NotLibOp>(
524  rewriter, loc, {one, one});
525  rewriter.create<calyx::AssignOp>(loc, notLibOp.getIn(), signal);
526  rewriter.create<calyx::AssignOp>(loc, reg.getIn(), notLibOp.getOut());
527  getState<ComponentLoweringState>().registerEvaluatingGroup(
528  notLibOp.getOut(), group);
529  } else
530  rewriter.create<calyx::AssignOp>(loc, reg.getIn(), signal);
531  return reg;
532  };
533 };
534 
535 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
536  memref::LoadOp loadOp) const {
537  Value memref = loadOp.getMemref();
538  auto memoryInterface =
539  getState<ComponentLoweringState>().getMemoryInterface(memref);
540  auto group = createGroupForOp<calyx::GroupOp>(rewriter, loadOp);
541  assignAddressPorts(rewriter, loadOp.getLoc(), group, memoryInterface,
542  loadOp.getIndices());
543 
544  rewriter.setInsertionPointToEnd(group.getBodyBlock());
545 
546  bool needReg = true;
547  Value res;
548  Value regWriteEn =
549  createConstant(loadOp.getLoc(), rewriter, getComponent(), 1, 1);
550  if (memoryInterface.readEnOpt().has_value()) {
551  auto oneI1 =
552  calyx::createConstant(loadOp.getLoc(), rewriter, getComponent(), 1, 1);
553  rewriter.create<calyx::AssignOp>(loadOp.getLoc(), memoryInterface.readEn(),
554  oneI1);
555  regWriteEn = memoryInterface.done();
556  if (calyx::noStoresToMemory(memref) &&
557  calyx::singleLoadFromMemory(memref)) {
558  // Single load from memory; we do not need to write the output to a
559  // register. The readData value will be held until readEn is asserted
560  // again
561  needReg = false;
562  rewriter.create<calyx::GroupDoneOp>(loadOp.getLoc(),
563  memoryInterface.done());
564  // We refrain from replacing the loadOp result with
565  // memoryInterface.readData, since multiple loadOp's need to be converted
566  // to a single memory's ReadData. If this replacement is done now, we lose
567  // the link between which SSA memref::LoadOp values map to which groups
568  // for loading a value from the Calyx memory. At this point of lowering,
569  // we keep the memref::LoadOp SSA value, and do value replacement _after_
570  // control has been generated (see LateSSAReplacement). This is *vital*
571  // for things such as calyx::InlineCombGroups to be able to properly track
572  // which memory assignment groups belong to which accesses.
573  res = loadOp.getResult();
574  }
575  } else if (memoryInterface.contentEnOpt().has_value()) {
576  auto oneI1 =
577  calyx::createConstant(loadOp.getLoc(), rewriter, getComponent(), 1, 1);
578  auto zeroI1 =
579  calyx::createConstant(loadOp.getLoc(), rewriter, getComponent(), 1, 0);
580  rewriter.create<calyx::AssignOp>(loadOp.getLoc(),
581  memoryInterface.contentEn(), oneI1);
582  rewriter.create<calyx::AssignOp>(loadOp.getLoc(), memoryInterface.writeEn(),
583  zeroI1);
584  regWriteEn = memoryInterface.done();
585  if (calyx::noStoresToMemory(memref) &&
586  calyx::singleLoadFromMemory(memref)) {
587  // Single load from memory; we do not need to write the output to a
588  // register. The readData value will be held until contentEn is asserted
589  // again
590  needReg = false;
591  rewriter.create<calyx::GroupDoneOp>(loadOp.getLoc(),
592  memoryInterface.done());
593  // We refrain from replacing the loadOp result with
594  // memoryInterface.readData, since multiple loadOp's need to be converted
595  // to a single memory's ReadData. If this replacement is done now, we lose
596  // the link between which SSA memref::LoadOp values map to which groups
597  // for loading a value from the Calyx memory. At this point of lowering,
598  // we keep the memref::LoadOp SSA value, and do value replacement _after_
599  // control has been generated (see LateSSAReplacement). This is *vital*
600  // for things such as calyx::InlineCombGroups to be able to properly track
601  // which memory assignment groups belong to which accesses.
602  res = loadOp.getResult();
603  }
604  }
605 
606  if (needReg) {
607  // Multiple loads from the same memory; In this case, we _may_ have a
608  // structural hazard in the design we generate. To get around this, we
609  // conservatively place a register in front of each load operation, and
610  // replace all uses of the loaded value with the register output. Reading
611  // for sequential memories will cause a read to take at least 2 cycles,
612  // but it will usually be better because combinational reads on memories
613  // can significantly decrease the maximum achievable frequency.
614  auto reg = createRegister(
615  loadOp.getLoc(), rewriter, getComponent(),
616  loadOp.getMemRefType().getElementTypeBitWidth(),
617  getState<ComponentLoweringState>().getUniqueName("load"));
618  rewriter.setInsertionPointToEnd(group.getBodyBlock());
619  rewriter.create<calyx::AssignOp>(loadOp.getLoc(), reg.getIn(),
620  memoryInterface.readData());
621  rewriter.create<calyx::AssignOp>(loadOp.getLoc(), reg.getWriteEn(),
622  regWriteEn);
623  rewriter.create<calyx::GroupDoneOp>(loadOp.getLoc(), reg.getDone());
624  loadOp.getResult().replaceAllUsesWith(reg.getOut());
625  res = reg.getOut();
626  }
627 
628  getState<ComponentLoweringState>().registerEvaluatingGroup(res, group);
629  getState<ComponentLoweringState>().addBlockScheduleable(loadOp->getBlock(),
630  group);
631  return success();
632 }
633 
634 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
635  memref::StoreOp storeOp) const {
636  auto memoryInterface = getState<ComponentLoweringState>().getMemoryInterface(
637  storeOp.getMemref());
638  auto group = createGroupForOp<calyx::GroupOp>(rewriter, storeOp);
639 
640  // This is a sequential group, so register it as being scheduleable for the
641  // block.
642  getState<ComponentLoweringState>().addBlockScheduleable(storeOp->getBlock(),
643  group);
644  assignAddressPorts(rewriter, storeOp.getLoc(), group, memoryInterface,
645  storeOp.getIndices());
646  rewriter.setInsertionPointToEnd(group.getBodyBlock());
647  rewriter.create<calyx::AssignOp>(
648  storeOp.getLoc(), memoryInterface.writeData(), storeOp.getValueToStore());
649  rewriter.create<calyx::AssignOp>(
650  storeOp.getLoc(), memoryInterface.writeEn(),
651  createConstant(storeOp.getLoc(), rewriter, getComponent(), 1, 1));
652  if (memoryInterface.contentEnOpt().has_value()) {
653  // If memory has content enable, it must be asserted when writing
654  rewriter.create<calyx::AssignOp>(
655  storeOp.getLoc(), memoryInterface.contentEn(),
656  createConstant(storeOp.getLoc(), rewriter, getComponent(), 1, 1));
657  }
658  rewriter.create<calyx::GroupDoneOp>(storeOp.getLoc(), memoryInterface.done());
659 
660  return success();
661 }
662 
663 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
664  MulIOp mul) const {
665  Location loc = mul.getLoc();
666  Type width = mul.getResult().getType(), one = rewriter.getI1Type();
667  auto mulPipe =
668  getState<ComponentLoweringState>()
669  .getNewLibraryOpInstance<calyx::MultPipeLibOp>(
670  rewriter, loc, {one, one, one, width, width, width, one});
671  return buildLibraryBinaryPipeOp<calyx::MultPipeLibOp>(
672  rewriter, mul, mulPipe,
673  /*out=*/mulPipe.getOut());
674 }
675 
676 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
677  DivUIOp div) const {
678  Location loc = div.getLoc();
679  Type width = div.getResult().getType(), one = rewriter.getI1Type();
680  auto divPipe =
681  getState<ComponentLoweringState>()
682  .getNewLibraryOpInstance<calyx::DivUPipeLibOp>(
683  rewriter, loc, {one, one, one, width, width, width, one});
684  return buildLibraryBinaryPipeOp<calyx::DivUPipeLibOp>(
685  rewriter, div, divPipe,
686  /*out=*/divPipe.getOut());
687 }
688 
689 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
690  DivSIOp div) const {
691  Location loc = div.getLoc();
692  Type width = div.getResult().getType(), one = rewriter.getI1Type();
693  auto divPipe =
694  getState<ComponentLoweringState>()
695  .getNewLibraryOpInstance<calyx::DivSPipeLibOp>(
696  rewriter, loc, {one, one, one, width, width, width, one});
697  return buildLibraryBinaryPipeOp<calyx::DivSPipeLibOp>(
698  rewriter, div, divPipe,
699  /*out=*/divPipe.getOut());
700 }
701 
702 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
703  RemUIOp rem) const {
704  Location loc = rem.getLoc();
705  Type width = rem.getResult().getType(), one = rewriter.getI1Type();
706  auto remPipe =
707  getState<ComponentLoweringState>()
708  .getNewLibraryOpInstance<calyx::RemUPipeLibOp>(
709  rewriter, loc, {one, one, one, width, width, width, one});
710  return buildLibraryBinaryPipeOp<calyx::RemUPipeLibOp>(
711  rewriter, rem, remPipe,
712  /*out=*/remPipe.getOut());
713 }
714 
715 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
716  RemSIOp rem) const {
717  Location loc = rem.getLoc();
718  Type width = rem.getResult().getType(), one = rewriter.getI1Type();
719  auto remPipe =
720  getState<ComponentLoweringState>()
721  .getNewLibraryOpInstance<calyx::RemSPipeLibOp>(
722  rewriter, loc, {one, one, one, width, width, width, one});
723  return buildLibraryBinaryPipeOp<calyx::RemSPipeLibOp>(
724  rewriter, rem, remPipe,
725  /*out=*/remPipe.getOut());
726 }
727 
728 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
729  AddFOp addf) const {
730  Location loc = addf.getLoc();
731  IntegerType one = rewriter.getI1Type(), three = rewriter.getIntegerType(3),
732  five = rewriter.getIntegerType(5),
733  width = rewriter.getIntegerType(
734  addf.getType().getIntOrFloatBitWidth());
735  auto addFOp =
736  getState<ComponentLoweringState>()
737  .getNewLibraryOpInstance<calyx::AddFOpIEEE754>(
738  rewriter, loc,
739  {one, one, one, one, one, width, width, three, width, five, one});
740  return buildLibraryBinaryPipeOp<calyx::AddFOpIEEE754>(rewriter, addf, addFOp,
741  addFOp.getOut());
742 }
743 
744 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
745  MulFOp mulf) const {
746  Location loc = mulf.getLoc();
747  IntegerType one = rewriter.getI1Type(), three = rewriter.getIntegerType(3),
748  five = rewriter.getIntegerType(5),
749  width = rewriter.getIntegerType(
750  mulf.getType().getIntOrFloatBitWidth());
751  auto mulFOp =
752  getState<ComponentLoweringState>()
753  .getNewLibraryOpInstance<calyx::MulFOpIEEE754>(
754  rewriter, loc,
755  {one, one, one, one, width, width, three, width, five, one});
756  return buildLibraryBinaryPipeOp<calyx::MulFOpIEEE754>(rewriter, mulf, mulFOp,
757  mulFOp.getOut());
758 }
759 
760 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
761  CmpFOp cmpf) const {
762  Location loc = cmpf.getLoc();
763  IntegerType one = rewriter.getI1Type(), five = rewriter.getIntegerType(5),
764  width = rewriter.getIntegerType(
765  cmpf.getLhs().getType().getIntOrFloatBitWidth());
766  auto calyxCmpFOp = getState<ComponentLoweringState>()
767  .getNewLibraryOpInstance<calyx::CompareFOpIEEE754>(
768  rewriter, loc,
769  {one, one, one, width, width, one, one, one, one,
770  one, five, one});
771  hw::ConstantOp c0 = createConstant(loc, rewriter, getComponent(), 1, 0);
772  hw::ConstantOp c1 = createConstant(loc, rewriter, getComponent(), 1, 1);
773  rewriter.setInsertionPointToStart(getComponent().getBodyBlock());
774 
775  using calyx::PredicateInfo;
776  using CombLogic = PredicateInfo::CombLogic;
777  using Port = PredicateInfo::InputPorts::Port;
778  PredicateInfo info = calyx::getPredicateInfo(cmpf.getPredicate());
779  if (info.logic == CombLogic::None) {
780  if (cmpf.getPredicate() == CmpFPredicate::AlwaysTrue) {
781  cmpf.getResult().replaceAllUsesWith(c1);
782  return success();
783  }
784 
785  if (cmpf.getPredicate() == CmpFPredicate::AlwaysFalse) {
786  cmpf.getResult().replaceAllUsesWith(c0);
787  return success();
788  }
789  }
790 
791  // General case
792  StringRef opName = cmpf.getOperationName().split(".").second;
793  auto reg =
794  createRegister(loc, rewriter, getComponent(), 1,
795  getState<ComponentLoweringState>().getUniqueName(opName));
796 
797  // Operation pipelines are not combinational, so a GroupOp is required.
798  auto group = createGroupForOp<calyx::GroupOp>(rewriter, cmpf);
799  OpBuilder builder(group->getRegion(0));
800  getState<ComponentLoweringState>().addBlockScheduleable(cmpf->getBlock(),
801  group);
802 
803  rewriter.setInsertionPointToEnd(group.getBodyBlock());
804  rewriter.create<calyx::AssignOp>(loc, calyxCmpFOp.getLeft(), cmpf.getLhs());
805  rewriter.create<calyx::AssignOp>(loc, calyxCmpFOp.getRight(), cmpf.getRhs());
806 
807  bool signalingFlag = false;
808  switch (cmpf.getPredicate()) {
809  case CmpFPredicate::UGT:
810  case CmpFPredicate::UGE:
811  case CmpFPredicate::ULT:
812  case CmpFPredicate::ULE:
813  case CmpFPredicate::OGT:
814  case CmpFPredicate::OGE:
815  case CmpFPredicate::OLT:
816  case CmpFPredicate::OLE:
817  signalingFlag = true;
818  break;
819  case CmpFPredicate::UEQ:
820  case CmpFPredicate::UNE:
821  case CmpFPredicate::OEQ:
822  case CmpFPredicate::ONE:
823  case CmpFPredicate::UNO:
824  case CmpFPredicate::ORD:
825  case CmpFPredicate::AlwaysTrue:
826  case CmpFPredicate::AlwaysFalse:
827  signalingFlag = false;
828  break;
829  }
830 
831  // The IEEE Standard mandates that equality comparisons ordinarily are quiet,
832  // while inequality comparisons ordinarily are signaling.
833  rewriter.create<calyx::AssignOp>(loc, calyxCmpFOp.getSignaling(),
834  signalingFlag ? c1 : c0);
835 
836  // Prepare signals and create registers
837  SmallVector<calyx::RegisterOp> inputRegs;
838  for (const auto &input : info.inputPorts) {
839  Value signal;
840  switch (input.port) {
841  case Port::Eq: {
842  signal = calyxCmpFOp.getEq();
843  break;
844  }
845  case Port::Gt: {
846  signal = calyxCmpFOp.getGt();
847  break;
848  }
849  case Port::Lt: {
850  signal = calyxCmpFOp.getLt();
851  break;
852  }
853  case Port::Unordered: {
854  signal = calyxCmpFOp.getUnordered();
855  break;
856  }
857  }
858  std::string nameSuffix =
859  (input.port == PredicateInfo::InputPorts::Port::Unordered)
860  ? "unordered_port"
861  : "compare_port";
862  auto signalReg = createSignalRegister(rewriter, signal, input.invert,
863  nameSuffix, calyxCmpFOp, group);
864  inputRegs.push_back(signalReg);
865  }
866 
867  // Create the output logical operation
868  Value outputValue, doneValue;
869  switch (info.logic) {
870  case CombLogic::None: {
871  // it's guaranteed to be either ORD or UNO
872  outputValue = inputRegs[0].getOut();
873  doneValue = inputRegs[0].getOut();
874  break;
875  }
876  case CombLogic::And: {
877  auto outputLibOp = getState<ComponentLoweringState>()
878  .getNewLibraryOpInstance<calyx::AndLibOp>(
879  rewriter, loc, {one, one, one});
880  rewriter.create<calyx::AssignOp>(loc, outputLibOp.getLeft(),
881  inputRegs[0].getOut());
882  rewriter.create<calyx::AssignOp>(loc, outputLibOp.getRight(),
883  inputRegs[1].getOut());
884 
885  outputValue = outputLibOp.getOut();
886  break;
887  }
888  case CombLogic::Or: {
889  auto outputLibOp = getState<ComponentLoweringState>()
890  .getNewLibraryOpInstance<calyx::OrLibOp>(
891  rewriter, loc, {one, one, one});
892  rewriter.create<calyx::AssignOp>(loc, outputLibOp.getLeft(),
893  inputRegs[0].getOut());
894  rewriter.create<calyx::AssignOp>(loc, outputLibOp.getRight(),
895  inputRegs[1].getOut());
896 
897  outputValue = outputLibOp.getOut();
898  break;
899  }
900  }
901 
902  if (info.logic != CombLogic::None) {
903  auto doneLibOp = getState<ComponentLoweringState>()
904  .getNewLibraryOpInstance<calyx::AndLibOp>(
905  rewriter, loc, {one, one, one});
906  rewriter.create<calyx::AssignOp>(loc, doneLibOp.getLeft(),
907  inputRegs[0].getDone());
908  rewriter.create<calyx::AssignOp>(loc, doneLibOp.getRight(),
909  inputRegs[1].getDone());
910  doneValue = doneLibOp.getOut();
911  }
912 
913  // Write to the output register
914  rewriter.create<calyx::AssignOp>(loc, reg.getIn(), outputValue);
915  rewriter.create<calyx::AssignOp>(loc, reg.getWriteEn(), doneValue);
916 
917  // Set the go and done signal
918  rewriter.create<calyx::AssignOp>(
919  loc, calyxCmpFOp.getGo(), c1,
920  comb::createOrFoldNot(loc, calyxCmpFOp.getDone(), builder));
921  rewriter.create<calyx::GroupDoneOp>(loc, reg.getDone());
922 
923  cmpf.getResult().replaceAllUsesWith(reg.getOut());
924 
925  // Register evaluating groups
926  getState<ComponentLoweringState>().registerEvaluatingGroup(outputValue,
927  group);
928  getState<ComponentLoweringState>().registerEvaluatingGroup(doneValue, group);
929  getState<ComponentLoweringState>().registerEvaluatingGroup(
930  calyxCmpFOp.getLeft(), group);
931  getState<ComponentLoweringState>().registerEvaluatingGroup(
932  calyxCmpFOp.getRight(), group);
933 
934  return success();
935 }
936 
937 template <typename TAllocOp>
938 static LogicalResult buildAllocOp(ComponentLoweringState &componentState,
939  PatternRewriter &rewriter, TAllocOp allocOp) {
940  rewriter.setInsertionPointToStart(
941  componentState.getComponentOp().getBodyBlock());
942  MemRefType memtype = allocOp.getType();
943  SmallVector<int64_t> addrSizes;
944  SmallVector<int64_t> sizes;
945  for (int64_t dim : memtype.getShape()) {
946  sizes.push_back(dim);
947  addrSizes.push_back(calyx::handleZeroWidth(dim));
948  }
949  // If memref has no size (e.g., memref<i32>) create a 1 dimensional memory of
950  // size 1.
951  if (sizes.empty() && addrSizes.empty()) {
952  sizes.push_back(1);
953  addrSizes.push_back(1);
954  }
955  auto memoryOp = rewriter.create<calyx::SeqMemoryOp>(
956  allocOp.getLoc(), componentState.getUniqueName("mem"),
957  memtype.getElementType().getIntOrFloatBitWidth(), sizes, addrSizes);
958 
959  // Externalize memories conditionally (only in the top-level component because
960  // Calyx compiler requires it as a well-formness check).
961  memoryOp->setAttr("external",
962  IntegerAttr::get(rewriter.getI1Type(), llvm::APInt(1, 1)));
963  componentState.registerMemoryInterface(allocOp.getResult(),
964  calyx::MemoryInterface(memoryOp));
965  return success();
966 }
967 
968 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
969  memref::AllocOp allocOp) const {
970  return buildAllocOp(getState<ComponentLoweringState>(), rewriter, allocOp);
971 }
972 
973 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
974  memref::AllocaOp allocOp) const {
975  return buildAllocOp(getState<ComponentLoweringState>(), rewriter, allocOp);
976 }
977 
978 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
979  scf::YieldOp yieldOp) const {
980  if (yieldOp.getOperands().empty()) {
981  // If yield operands are empty, we assume we have a for loop.
982  auto forOp = dyn_cast<scf::ForOp>(yieldOp->getParentOp());
983  assert(forOp && "Empty yieldOps should only be located within ForOps");
984  ScfForOp forOpInterface(forOp);
985 
986  // Get the ForLoop's Induction Register.
987  auto inductionReg =
988  getState<ComponentLoweringState>().getForLoopIterReg(forOpInterface, 0);
989 
990  Type regWidth = inductionReg.getOut().getType();
991  // Adder should have same width as the inductionReg.
992  SmallVector<Type> types(3, regWidth);
993  auto addOp = getState<ComponentLoweringState>()
994  .getNewLibraryOpInstance<calyx::AddLibOp>(
995  rewriter, forOp.getLoc(), types);
996 
997  auto directions = addOp.portDirections();
998  // For an add operation, we expect two input ports and one output port
999  SmallVector<Value, 2> opInputPorts;
1000  Value opOutputPort;
1001  for (auto dir : enumerate(directions)) {
1002  switch (dir.value()) {
1003  case calyx::Direction::Input: {
1004  opInputPorts.push_back(addOp.getResult(dir.index()));
1005  break;
1006  }
1007  case calyx::Direction::Output: {
1008  opOutputPort = addOp.getResult(dir.index());
1009  break;
1010  }
1011  }
1012  }
1013 
1014  // "Latch Group" increments inductionReg by forLoop's step value.
1015  calyx::ComponentOp componentOp =
1016  getState<ComponentLoweringState>().getComponentOp();
1017  SmallVector<StringRef, 4> groupIdentifier = {
1018  "incr", getState<ComponentLoweringState>().getUniqueName(forOp),
1019  "induction", "var"};
1020  auto groupOp = calyx::createGroup<calyx::GroupOp>(
1021  rewriter, componentOp, forOp.getLoc(),
1022  llvm::join(groupIdentifier, "_"));
1023  rewriter.setInsertionPointToEnd(groupOp.getBodyBlock());
1024 
1025  // Assign inductionReg.out to the left port of the adder.
1026  Value leftOp = opInputPorts.front();
1027  rewriter.create<calyx::AssignOp>(forOp.getLoc(), leftOp,
1028  inductionReg.getOut());
1029  // Assign forOp.getConstantStep to the right port of the adder.
1030  Value rightOp = opInputPorts.back();
1031  rewriter.create<calyx::AssignOp>(
1032  forOp.getLoc(), rightOp,
1033  createConstant(forOp->getLoc(), rewriter, componentOp,
1034  regWidth.getIntOrFloatBitWidth(),
1035  forOp.getConstantStep().value().getSExtValue()));
1036  // Assign adder's output port to inductionReg.
1037  buildAssignmentsForRegisterWrite(rewriter, groupOp, componentOp,
1038  inductionReg, opOutputPort);
1039  // Set group as For Loop's "latch" group.
1040  getState<ComponentLoweringState>().setForLoopLatchGroup(forOpInterface,
1041  groupOp);
1042  getState<ComponentLoweringState>().registerEvaluatingGroup(opOutputPort,
1043  groupOp);
1044  return success();
1045  }
1046  // If yieldOp for a for loop is not empty, then we do not transform for loop.
1047  if (dyn_cast<scf::ForOp>(yieldOp->getParentOp())) {
1048  return yieldOp.getOperation()->emitError()
1049  << "Currently do not support non-empty yield operations inside for "
1050  "loops. Run --scf-for-to-while before running --scf-to-calyx.";
1051  }
1052 
1053  if (auto whileOp = dyn_cast<scf::WhileOp>(yieldOp->getParentOp())) {
1054  ScfWhileOp whileOpInterface(whileOp);
1055 
1056  auto assignGroup =
1057  getState<ComponentLoweringState>().buildWhileLoopIterArgAssignments(
1058  rewriter, whileOpInterface,
1059  getState<ComponentLoweringState>().getComponentOp(),
1060  getState<ComponentLoweringState>().getUniqueName(whileOp) +
1061  "_latch",
1062  yieldOp->getOpOperands());
1063  getState<ComponentLoweringState>().setWhileLoopLatchGroup(whileOpInterface,
1064  assignGroup);
1065  return success();
1066  }
1067 
1068  if (auto ifOp = dyn_cast<scf::IfOp>(yieldOp->getParentOp())) {
1069  auto resultRegs = getState<ComponentLoweringState>().getResultRegs(ifOp);
1070 
1071  if (yieldOp->getParentRegion() == &ifOp.getThenRegion()) {
1072  auto thenGroup = getState<ComponentLoweringState>().getThenGroup(ifOp);
1073  for (auto op : enumerate(yieldOp.getOperands())) {
1074  auto resultReg =
1075  getState<ComponentLoweringState>().getResultRegs(ifOp, op.index());
1077  rewriter, thenGroup,
1078  getState<ComponentLoweringState>().getComponentOp(), resultReg,
1079  op.value());
1080  getState<ComponentLoweringState>().registerEvaluatingGroup(
1081  ifOp.getResult(op.index()), thenGroup);
1082  }
1083  }
1084 
1085  if (!ifOp.getElseRegion().empty() &&
1086  (yieldOp->getParentRegion() == &ifOp.getElseRegion())) {
1087  auto elseGroup = getState<ComponentLoweringState>().getElseGroup(ifOp);
1088  for (auto op : enumerate(yieldOp.getOperands())) {
1089  auto resultReg =
1090  getState<ComponentLoweringState>().getResultRegs(ifOp, op.index());
1092  rewriter, elseGroup,
1093  getState<ComponentLoweringState>().getComponentOp(), resultReg,
1094  op.value());
1095  getState<ComponentLoweringState>().registerEvaluatingGroup(
1096  ifOp.getResult(op.index()), elseGroup);
1097  }
1098  }
1099  }
1100  return success();
1101 }
1102 
1103 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1104  BranchOpInterface brOp) const {
1105  /// Branch argument passing group creation
1106  /// Branch operands are passed through registers. In BuildBasicBlockRegs we
1107  /// created registers for all branch arguments of each block. We now
1108  /// create groups for assigning values to these registers.
1109  Block *srcBlock = brOp->getBlock();
1110  for (auto succBlock : enumerate(brOp->getSuccessors())) {
1111  auto succOperands = brOp.getSuccessorOperands(succBlock.index());
1112  if (succOperands.empty())
1113  continue;
1114  // Create operand passing group
1115  std::string groupName = loweringState().blockName(srcBlock) + "_to_" +
1116  loweringState().blockName(succBlock.value());
1117  auto groupOp = calyx::createGroup<calyx::GroupOp>(rewriter, getComponent(),
1118  brOp.getLoc(), groupName);
1119  // Fetch block argument registers associated with the basic block
1120  auto dstBlockArgRegs =
1121  getState<ComponentLoweringState>().getBlockArgRegs(succBlock.value());
1122  // Create register assignment for each block argument
1123  for (auto arg : enumerate(succOperands.getForwardedOperands())) {
1124  auto reg = dstBlockArgRegs[arg.index()];
1126  rewriter, groupOp,
1127  getState<ComponentLoweringState>().getComponentOp(), reg,
1128  arg.value());
1129  }
1130  /// Register the group as a block argument group, to be executed
1131  /// when entering the successor block from this block (srcBlock).
1132  getState<ComponentLoweringState>().addBlockArgGroup(
1133  srcBlock, succBlock.value(), groupOp);
1134  }
1135  return success();
1136 }
1137 
1138 /// For each return statement, we create a new group for assigning to the
1139 /// previously created return value registers.
1140 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1141  ReturnOp retOp) const {
1142  if (retOp.getNumOperands() == 0)
1143  return success();
1144 
1145  std::string groupName =
1146  getState<ComponentLoweringState>().getUniqueName("ret_assign");
1147  auto groupOp = calyx::createGroup<calyx::GroupOp>(rewriter, getComponent(),
1148  retOp.getLoc(), groupName);
1149  for (auto op : enumerate(retOp.getOperands())) {
1150  auto reg = getState<ComponentLoweringState>().getReturnReg(op.index());
1152  rewriter, groupOp, getState<ComponentLoweringState>().getComponentOp(),
1153  reg, op.value());
1154  }
1155  /// Schedule group for execution for when executing the return op block.
1156  getState<ComponentLoweringState>().addBlockScheduleable(retOp->getBlock(),
1157  groupOp);
1158  return success();
1159 }
1160 
1161 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1162  arith::ConstantOp constOp) const {
1163  if (isa<IntegerType>(constOp.getType())) {
1164  /// Move constant operations to the compOp body as hw::ConstantOp's.
1165  APInt value;
1166  calyx::matchConstantOp(constOp, value);
1167  auto hwConstOp =
1168  rewriter.replaceOpWithNewOp<hw::ConstantOp>(constOp, value);
1169  hwConstOp->moveAfter(getComponent().getBodyBlock(),
1170  getComponent().getBodyBlock()->begin());
1171  } else {
1172  std::string name = getState<ComponentLoweringState>().getUniqueName("cst");
1173  auto floatAttr = cast<FloatAttr>(constOp.getValueAttr());
1174  auto intType =
1175  rewriter.getIntegerType(floatAttr.getType().getIntOrFloatBitWidth());
1176  auto calyxConstOp = rewriter.create<calyx::ConstantOp>(
1177  constOp.getLoc(), name, floatAttr, intType);
1178  calyxConstOp->moveAfter(getComponent().getBodyBlock(),
1179  getComponent().getBodyBlock()->begin());
1180  rewriter.replaceAllUsesWith(constOp, calyxConstOp.getOut());
1181  }
1182 
1183  return success();
1184 }
1185 
1186 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1187  AddIOp op) const {
1188  return buildLibraryOp<calyx::CombGroupOp, calyx::AddLibOp>(rewriter, op);
1189 }
1190 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1191  SubIOp op) const {
1192  return buildLibraryOp<calyx::CombGroupOp, calyx::SubLibOp>(rewriter, op);
1193 }
1194 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1195  ShRUIOp op) const {
1196  return buildLibraryOp<calyx::CombGroupOp, calyx::RshLibOp>(rewriter, op);
1197 }
1198 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1199  ShRSIOp op) const {
1200  return buildLibraryOp<calyx::CombGroupOp, calyx::SrshLibOp>(rewriter, op);
1201 }
1202 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1203  ShLIOp op) const {
1204  return buildLibraryOp<calyx::CombGroupOp, calyx::LshLibOp>(rewriter, op);
1205 }
1206 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1207  AndIOp op) const {
1208  return buildLibraryOp<calyx::CombGroupOp, calyx::AndLibOp>(rewriter, op);
1209 }
1210 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1211  OrIOp op) const {
1212  return buildLibraryOp<calyx::CombGroupOp, calyx::OrLibOp>(rewriter, op);
1213 }
1214 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1215  XOrIOp op) const {
1216  return buildLibraryOp<calyx::CombGroupOp, calyx::XorLibOp>(rewriter, op);
1217 }
1218 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1219  SelectOp op) const {
1220  return buildLibraryOp<calyx::CombGroupOp, calyx::MuxLibOp>(rewriter, op);
1221 }
1222 
1223 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1224  CmpIOp op) const {
1225  switch (op.getPredicate()) {
1226  case CmpIPredicate::eq:
1227  return buildLibraryOp<calyx::CombGroupOp, calyx::EqLibOp>(rewriter, op);
1228  case CmpIPredicate::ne:
1229  return buildLibraryOp<calyx::CombGroupOp, calyx::NeqLibOp>(rewriter, op);
1230  case CmpIPredicate::uge:
1231  return buildLibraryOp<calyx::CombGroupOp, calyx::GeLibOp>(rewriter, op);
1232  case CmpIPredicate::ult:
1233  return buildLibraryOp<calyx::CombGroupOp, calyx::LtLibOp>(rewriter, op);
1234  case CmpIPredicate::ugt:
1235  return buildLibraryOp<calyx::CombGroupOp, calyx::GtLibOp>(rewriter, op);
1236  case CmpIPredicate::ule:
1237  return buildLibraryOp<calyx::CombGroupOp, calyx::LeLibOp>(rewriter, op);
1238  case CmpIPredicate::sge:
1239  return buildLibraryOp<calyx::CombGroupOp, calyx::SgeLibOp>(rewriter, op);
1240  case CmpIPredicate::slt:
1241  return buildLibraryOp<calyx::CombGroupOp, calyx::SltLibOp>(rewriter, op);
1242  case CmpIPredicate::sgt:
1243  return buildLibraryOp<calyx::CombGroupOp, calyx::SgtLibOp>(rewriter, op);
1244  case CmpIPredicate::sle:
1245  return buildLibraryOp<calyx::CombGroupOp, calyx::SleLibOp>(rewriter, op);
1246  }
1247  llvm_unreachable("unsupported comparison predicate");
1248 }
1249 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1250  TruncIOp op) const {
1251  return buildLibraryOp<calyx::CombGroupOp, calyx::SliceLibOp>(
1252  rewriter, op, {op.getOperand().getType()}, {op.getType()});
1253 }
1254 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1255  ExtUIOp op) const {
1256  return buildLibraryOp<calyx::CombGroupOp, calyx::PadLibOp>(
1257  rewriter, op, {op.getOperand().getType()}, {op.getType()});
1258 }
1259 
1260 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1261  ExtSIOp op) const {
1262  return buildLibraryOp<calyx::CombGroupOp, calyx::ExtSILibOp>(
1263  rewriter, op, {op.getOperand().getType()}, {op.getType()});
1264 }
1265 
1266 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1267  IndexCastOp op) const {
1268  Type sourceType = calyx::convIndexType(rewriter, op.getOperand().getType());
1269  Type targetType = calyx::convIndexType(rewriter, op.getResult().getType());
1270  unsigned targetBits = targetType.getIntOrFloatBitWidth();
1271  unsigned sourceBits = sourceType.getIntOrFloatBitWidth();
1272  LogicalResult res = success();
1273 
1274  if (targetBits == sourceBits) {
1275  /// Drop the index cast and replace uses of the target value with the source
1276  /// value.
1277  op.getResult().replaceAllUsesWith(op.getOperand());
1278  } else {
1279  /// pad/slice the source operand.
1280  if (sourceBits > targetBits)
1281  res = buildLibraryOp<calyx::CombGroupOp, calyx::SliceLibOp>(
1282  rewriter, op, {sourceType}, {targetType});
1283  else
1284  res = buildLibraryOp<calyx::CombGroupOp, calyx::PadLibOp>(
1285  rewriter, op, {sourceType}, {targetType});
1286  }
1287  rewriter.eraseOp(op);
1288  return res;
1289 }
1290 
1291 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1292  scf::WhileOp whileOp) const {
1293  // Only need to add the whileOp to the BlockSchedulables scheduler interface.
1294  // Everything else was handled in the `BuildWhileGroups` pattern.
1295  ScfWhileOp scfWhileOp(whileOp);
1296  getState<ComponentLoweringState>().addBlockScheduleable(
1297  whileOp.getOperation()->getBlock(), WhileScheduleable{scfWhileOp});
1298  return success();
1299 }
1300 
1301 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1302  scf::ForOp forOp) const {
1303  // Only need to add the forOp to the BlockSchedulables scheduler interface.
1304  // Everything else was handled in the `BuildForGroups` pattern.
1305  ScfForOp scfForOp(forOp);
1306  // If we cannot compute the trip count of the for loop, then we should
1307  // emit an error saying to use --scf-for-to-while
1308  std::optional<uint64_t> bound = scfForOp.getBound();
1309  if (!bound.has_value()) {
1310  return scfForOp.getOperation()->emitError()
1311  << "Loop bound not statically known. Should "
1312  "transform into while loop using `--scf-for-to-while` before "
1313  "running --lower-scf-to-calyx.";
1314  }
1315  getState<ComponentLoweringState>().addBlockScheduleable(
1316  forOp.getOperation()->getBlock(), ForScheduleable{
1317  scfForOp,
1318  bound.value(),
1319  });
1320  return success();
1321 }
1322 
1323 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1324  scf::IfOp ifOp) const {
1325  getState<ComponentLoweringState>().addBlockScheduleable(
1326  ifOp.getOperation()->getBlock(), IfScheduleable{ifOp});
1327  return success();
1328 }
1329 
1330 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1331  scf::ReduceOp reduceOp) const {
1332  // we don't handle reduce operation and simply return success for now since
1333  // BuildParGroups would have already emitted an error and exited early
1334  // if a reduce operation was encountered.
1335  return success();
1336 }
1337 
1338 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1339  scf::ParallelOp parOp) const {
1340  getState<ComponentLoweringState>().addBlockScheduleable(
1341  parOp.getOperation()->getBlock(), ParScheduleable{parOp});
1342  return success();
1343 }
1344 
1345 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
1346  CallOp callOp) const {
1347  std::string instanceName = calyx::getInstanceName(callOp);
1348  calyx::InstanceOp instanceOp =
1349  getState<ComponentLoweringState>().getInstance(instanceName);
1350  SmallVector<Value, 4> outputPorts;
1351  auto portInfos = instanceOp.getReferencedComponent().getPortInfo();
1352  for (auto [idx, portInfo] : enumerate(portInfos)) {
1353  if (portInfo.direction == calyx::Direction::Output)
1354  outputPorts.push_back(instanceOp.getResult(idx));
1355  }
1356 
1357  // Replacing a CallOp results in the out port of the instance.
1358  for (auto [idx, result] : llvm::enumerate(callOp.getResults()))
1359  rewriter.replaceAllUsesWith(result, outputPorts[idx]);
1360 
1361  // CallScheduleanle requires an instance, while CallOp can be used to get the
1362  // input ports.
1363  getState<ComponentLoweringState>().addBlockScheduleable(
1364  callOp.getOperation()->getBlock(), CallScheduleable{instanceOp, callOp});
1365  return success();
1366 }
1367 
1368 /// Inlines Calyx ExecuteRegionOp operations within their parent blocks.
1369 /// An execution region op (ERO) is inlined by:
1370 /// i : add a sink basic block for all yield operations inside the
1371 /// ERO to jump to
1372 /// ii : Rewrite scf.yield calls inside the ERO to branch to the sink block
1373 /// iii: inline the ERO region
1374 /// TODO(#1850) evaluate the usefulness of this lowering pattern.
1376  : public OpRewritePattern<scf::ExecuteRegionOp> {
1377  using OpRewritePattern::OpRewritePattern;
1378 
1379  LogicalResult matchAndRewrite(scf::ExecuteRegionOp execOp,
1380  PatternRewriter &rewriter) const override {
1381  /// Determine type of "yield" operations inside the ERO.
1382  TypeRange yieldTypes = execOp.getResultTypes();
1383 
1384  /// Create sink basic block and rewrite uses of yield results to sink block
1385  /// arguments.
1386  rewriter.setInsertionPointAfter(execOp);
1387  auto *sinkBlock = rewriter.splitBlock(
1388  execOp->getBlock(),
1389  execOp.getOperation()->getIterator()->getNextNode()->getIterator());
1390  sinkBlock->addArguments(
1391  yieldTypes,
1392  SmallVector<Location, 4>(yieldTypes.size(), rewriter.getUnknownLoc()));
1393  for (auto res : enumerate(execOp.getResults()))
1394  res.value().replaceAllUsesWith(sinkBlock->getArgument(res.index()));
1395 
1396  /// Rewrite yield calls as branches.
1397  for (auto yieldOp :
1398  make_early_inc_range(execOp.getRegion().getOps<scf::YieldOp>())) {
1399  rewriter.setInsertionPointAfter(yieldOp);
1400  rewriter.replaceOpWithNewOp<BranchOp>(yieldOp, sinkBlock,
1401  yieldOp.getOperands());
1402  }
1403 
1404  /// Inline the regionOp.
1405  auto *preBlock = execOp->getBlock();
1406  auto *execOpEntryBlock = &execOp.getRegion().front();
1407  auto *postBlock = execOp->getBlock()->splitBlock(execOp);
1408  rewriter.inlineRegionBefore(execOp.getRegion(), postBlock);
1409  rewriter.mergeBlocks(postBlock, preBlock);
1410  rewriter.eraseOp(execOp);
1411 
1412  /// Finally, erase the unused entry block of the execOp region.
1413  rewriter.mergeBlocks(execOpEntryBlock, preBlock);
1414 
1415  return success();
1416  }
1417 };
1418 
1419 /// Creates a new Calyx component for each FuncOp in the program.
1421  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1422 
1423  LogicalResult
1425  PatternRewriter &rewriter) const override {
1426  /// Maintain a mapping between funcOp input arguments and the port index
1427  /// which the argument will eventually map to.
1428  DenseMap<Value, unsigned> funcOpArgRewrites;
1429 
1430  /// Maintain a mapping between funcOp output indexes and the component
1431  /// output port index which the return value will eventually map to.
1432  DenseMap<unsigned, unsigned> funcOpResultMapping;
1433 
1434  /// Maintain a mapping between an external memory argument (identified by a
1435  /// memref) and eventual component input- and output port indices that will
1436  /// map to the memory ports. The pair denotes the start index of the memory
1437  /// ports in the in- and output ports of the component. Ports are expected
1438  /// to be ordered in the same manner as they are added by
1439  /// calyx::appendPortsForExternalMemref.
1440  DenseMap<Value, std::pair<unsigned, unsigned>> extMemoryCompPortIndices;
1441 
1442  /// Create I/O ports. Maintain separate in/out port vectors to determine
1443  /// which port index each function argument will eventually map to.
1444  SmallVector<calyx::PortInfo> inPorts, outPorts;
1445  FunctionType funcType = funcOp.getFunctionType();
1446  for (auto arg : enumerate(funcOp.getArguments())) {
1447  if (!isa<MemRefType>(arg.value().getType())) {
1448  /// Single-port arguments
1449  std::string inName;
1450  if (auto portNameAttr = funcOp.getArgAttrOfType<StringAttr>(
1451  arg.index(), scfToCalyx::sPortNameAttr))
1452  inName = portNameAttr.str();
1453  else
1454  inName = "in" + std::to_string(arg.index());
1455  funcOpArgRewrites[arg.value()] = inPorts.size();
1456  inPorts.push_back(calyx::PortInfo{
1457  rewriter.getStringAttr(inName),
1458  calyx::convIndexType(rewriter, arg.value().getType()),
1460  DictionaryAttr::get(rewriter.getContext(), {})});
1461  }
1462  }
1463  for (auto res : enumerate(funcType.getResults())) {
1464  std::string resName;
1465  if (auto portNameAttr = funcOp.getResultAttrOfType<StringAttr>(
1466  res.index(), scfToCalyx::sPortNameAttr))
1467  resName = portNameAttr.str();
1468  else
1469  resName = "out" + std::to_string(res.index());
1470  funcOpResultMapping[res.index()] = outPorts.size();
1471 
1472  outPorts.push_back(calyx::PortInfo{
1473  rewriter.getStringAttr(resName),
1474  calyx::convIndexType(rewriter, res.value()), calyx::Direction::Output,
1475  DictionaryAttr::get(rewriter.getContext(), {})});
1476  }
1477 
1478  /// We've now recorded all necessary indices. Merge in- and output ports
1479  /// and add the required mandatory component ports.
1480  auto ports = inPorts;
1481  llvm::append_range(ports, outPorts);
1482  calyx::addMandatoryComponentPorts(rewriter, ports);
1483 
1484  /// Create a calyx::ComponentOp corresponding to the to-be-lowered function.
1485  auto compOp = rewriter.create<calyx::ComponentOp>(
1486  funcOp.getLoc(), rewriter.getStringAttr(funcOp.getSymName()), ports);
1487 
1488  std::string funcName = "func_" + funcOp.getSymName().str();
1489  rewriter.modifyOpInPlace(funcOp, [&]() { funcOp.setSymName(funcName); });
1490 
1491  /// Mark this component as the toplevel if it's the top-level function of
1492  /// the module.
1493  if (compOp.getName() == loweringState().getTopLevelFunction())
1494  compOp->setAttr("toplevel", rewriter.getUnitAttr());
1495 
1496  /// Store the function-to-component mapping.
1497  functionMapping[funcOp] = compOp;
1498  auto *compState = loweringState().getState<ComponentLoweringState>(compOp);
1499  compState->setFuncOpResultMapping(funcOpResultMapping);
1500 
1501  unsigned extMemCounter = 0;
1502  for (auto arg : enumerate(funcOp.getArguments())) {
1503  if (isa<MemRefType>(arg.value().getType())) {
1504  std::string memName =
1505  llvm::join_items("_", "arg_mem", std::to_string(extMemCounter++));
1506 
1507  rewriter.setInsertionPointToStart(compOp.getBodyBlock());
1508  MemRefType memtype = cast<MemRefType>(arg.value().getType());
1509  SmallVector<int64_t> addrSizes;
1510  SmallVector<int64_t> sizes;
1511  for (int64_t dim : memtype.getShape()) {
1512  sizes.push_back(dim);
1513  addrSizes.push_back(calyx::handleZeroWidth(dim));
1514  }
1515  if (sizes.empty() && addrSizes.empty()) {
1516  sizes.push_back(1);
1517  addrSizes.push_back(1);
1518  }
1519  auto memOp = rewriter.create<calyx::SeqMemoryOp>(
1520  funcOp.getLoc(), memName,
1521  memtype.getElementType().getIntOrFloatBitWidth(), sizes, addrSizes);
1522  // we don't set the memory to "external", which implies it's a reference
1523 
1524  compState->registerMemoryInterface(arg.value(),
1525  calyx::MemoryInterface(memOp));
1526  }
1527  }
1528 
1529  /// Rewrite funcOp SSA argument values to the CompOp arguments.
1530  for (auto &mapping : funcOpArgRewrites)
1531  mapping.getFirst().replaceAllUsesWith(
1532  compOp.getArgument(mapping.getSecond()));
1533 
1534  return success();
1535  }
1536 };
1537 
1538 /// In BuildWhileGroups, a register is created for each iteration argumenet of
1539 /// the while op. These registers are then written to on the while op
1540 /// terminating yield operation alongside before executing the whileOp in the
1541 /// schedule, to set the initial values of the argument registers.
1543  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1544 
1545  LogicalResult
1547  PatternRewriter &rewriter) const override {
1548  LogicalResult res = success();
1549  funcOp.walk([&](Operation *op) {
1550  // Only work on ops that support the ScfWhileOp.
1551  if (!isa<scf::WhileOp>(op))
1552  return WalkResult::advance();
1553 
1554  auto scfWhileOp = cast<scf::WhileOp>(op);
1555  ScfWhileOp whileOp(scfWhileOp);
1556 
1557  getState<ComponentLoweringState>().setUniqueName(whileOp.getOperation(),
1558  "while");
1559 
1560  /// Check for do-while loops.
1561  /// TODO(mortbopet) can we support these? for now, do not support loops
1562  /// where iterargs are changed in the 'before' region. scf.WhileOp also
1563  /// has support for different types of iter_args and return args which we
1564  /// also do not support; iter_args and while return values are placed in
1565  /// the same registers.
1566  for (auto barg :
1567  enumerate(scfWhileOp.getBefore().front().getArguments())) {
1568  auto condOp = scfWhileOp.getConditionOp().getArgs()[barg.index()];
1569  if (barg.value() != condOp) {
1570  res = whileOp.getOperation()->emitError()
1571  << loweringState().irName(barg.value())
1572  << " != " << loweringState().irName(condOp)
1573  << "do-while loops not supported; expected iter-args to "
1574  "remain untransformed in the 'before' region of the "
1575  "scf.while op.";
1576  return WalkResult::interrupt();
1577  }
1578  }
1579 
1580  /// Create iteration argument registers.
1581  /// The iteration argument registers will be referenced:
1582  /// - In the "before" part of the while loop, calculating the conditional,
1583  /// - In the "after" part of the while loop,
1584  /// - Outside the while loop, rewriting the while loop return values.
1585  for (auto arg : enumerate(whileOp.getBodyArgs())) {
1586  std::string name = getState<ComponentLoweringState>()
1587  .getUniqueName(whileOp.getOperation())
1588  .str() +
1589  "_arg" + std::to_string(arg.index());
1590  auto reg =
1591  createRegister(arg.value().getLoc(), rewriter, getComponent(),
1592  arg.value().getType().getIntOrFloatBitWidth(), name);
1593  getState<ComponentLoweringState>().addWhileLoopIterReg(whileOp, reg,
1594  arg.index());
1595  arg.value().replaceAllUsesWith(reg.getOut());
1596 
1597  /// Also replace uses in the "before" region of the while loop
1598  whileOp.getConditionBlock()
1599  ->getArgument(arg.index())
1600  .replaceAllUsesWith(reg.getOut());
1601  }
1602 
1603  /// Create iter args initial value assignment group(s), one per register.
1604  SmallVector<calyx::GroupOp> initGroups;
1605  auto numOperands = whileOp.getOperation()->getNumOperands();
1606  for (size_t i = 0; i < numOperands; ++i) {
1607  auto initGroupOp =
1608  getState<ComponentLoweringState>().buildWhileLoopIterArgAssignments(
1609  rewriter, whileOp,
1610  getState<ComponentLoweringState>().getComponentOp(),
1611  getState<ComponentLoweringState>().getUniqueName(
1612  whileOp.getOperation()) +
1613  "_init_" + std::to_string(i),
1614  whileOp.getOperation()->getOpOperand(i));
1615  initGroups.push_back(initGroupOp);
1616  }
1617 
1618  getState<ComponentLoweringState>().setWhileLoopInitGroups(whileOp,
1619  initGroups);
1620 
1621  return WalkResult::advance();
1622  });
1623  return res;
1624  }
1625 };
1626 
1627 /// In BuildForGroups, a register is created for the iteration argument of
1628 /// the for op. This register is then initialized to the lowerBound of the for
1629 /// loop in a group that executes the for loop.
1631  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1632 
1633  LogicalResult
1635  PatternRewriter &rewriter) const override {
1636  LogicalResult res = success();
1637  funcOp.walk([&](Operation *op) {
1638  // Only work on ops that support the ScfForOp.
1639  if (!isa<scf::ForOp>(op))
1640  return WalkResult::advance();
1641 
1642  auto scfForOp = cast<scf::ForOp>(op);
1643  ScfForOp forOp(scfForOp);
1644 
1645  getState<ComponentLoweringState>().setUniqueName(forOp.getOperation(),
1646  "for");
1647 
1648  // Create a register for the InductionVar, and set that Register as the
1649  // only IterReg for the For Loop
1650  auto inductionVar = forOp.getOperation().getInductionVar();
1651  SmallVector<std::string, 3> inductionVarIdentifiers = {
1652  getState<ComponentLoweringState>()
1653  .getUniqueName(forOp.getOperation())
1654  .str(),
1655  "induction", "var"};
1656  std::string name = llvm::join(inductionVarIdentifiers, "_");
1657  auto reg =
1658  createRegister(inductionVar.getLoc(), rewriter, getComponent(),
1659  inductionVar.getType().getIntOrFloatBitWidth(), name);
1660  getState<ComponentLoweringState>().addForLoopIterReg(forOp, reg, 0);
1661  inductionVar.replaceAllUsesWith(reg.getOut());
1662 
1663  // Create InitGroup that sets the InductionVar to LowerBound
1664  calyx::ComponentOp componentOp =
1665  getState<ComponentLoweringState>().getComponentOp();
1666  SmallVector<calyx::GroupOp> initGroups;
1667  SmallVector<std::string, 4> groupIdentifiers = {
1668  "init",
1669  getState<ComponentLoweringState>()
1670  .getUniqueName(forOp.getOperation())
1671  .str(),
1672  "induction", "var"};
1673  std::string groupName = llvm::join(groupIdentifiers, "_");
1674  auto groupOp = calyx::createGroup<calyx::GroupOp>(
1675  rewriter, componentOp, forOp.getLoc(), groupName);
1676  buildAssignmentsForRegisterWrite(rewriter, groupOp, componentOp, reg,
1677  forOp.getOperation().getLowerBound());
1678  initGroups.push_back(groupOp);
1679  getState<ComponentLoweringState>().setForLoopInitGroups(forOp,
1680  initGroups);
1681 
1682  return WalkResult::advance();
1683  });
1684  return res;
1685  }
1686 };
1687 
1689  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1690 
1691  LogicalResult
1693  PatternRewriter &rewriter) const override {
1694  LogicalResult res = success();
1695  funcOp.walk([&](Operation *op) {
1696  if (!isa<scf::IfOp>(op))
1697  return WalkResult::advance();
1698 
1699  auto scfIfOp = cast<scf::IfOp>(op);
1700 
1701  calyx::ComponentOp componentOp =
1702  getState<ComponentLoweringState>().getComponentOp();
1703 
1704  std::string thenGroupName =
1705  getState<ComponentLoweringState>().getUniqueName("then_br");
1706  auto thenGroupOp = calyx::createGroup<calyx::GroupOp>(
1707  rewriter, componentOp, scfIfOp.getLoc(), thenGroupName);
1708  getState<ComponentLoweringState>().setThenGroup(scfIfOp, thenGroupOp);
1709 
1710  if (!scfIfOp.getElseRegion().empty()) {
1711  std::string elseGroupName =
1712  getState<ComponentLoweringState>().getUniqueName("else_br");
1713  auto elseGroupOp = calyx::createGroup<calyx::GroupOp>(
1714  rewriter, componentOp, scfIfOp.getLoc(), elseGroupName);
1715  getState<ComponentLoweringState>().setElseGroup(scfIfOp, elseGroupOp);
1716  }
1717 
1718  for (auto ifOpRes : scfIfOp.getResults()) {
1719  auto reg = createRegister(
1720  scfIfOp.getLoc(), rewriter, getComponent(),
1721  ifOpRes.getType().getIntOrFloatBitWidth(),
1722  getState<ComponentLoweringState>().getUniqueName("if_res"));
1723  getState<ComponentLoweringState>().setResultRegs(
1724  scfIfOp, reg, ifOpRes.getResultNumber());
1725  }
1726 
1727  return WalkResult::advance();
1728  });
1729  return res;
1730  }
1731 };
1732 
1734  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1735 
1736  LogicalResult
1738  PatternRewriter &rewriter) const override {
1739  WalkResult walkResult = funcOp.walk([&](scf::ParallelOp scfParOp) {
1740  if (!scfParOp.getResults().empty()) {
1741  scfParOp.emitError(
1742  "Reduce operations in scf.parallel is not supported yet");
1743  return WalkResult::interrupt();
1744  }
1745 
1746  if (failed(partialEval(rewriter, scfParOp)))
1747  return WalkResult::interrupt();
1748 
1749  return WalkResult::advance();
1750  });
1751 
1752  return walkResult.wasInterrupted() ? failure() : success();
1753  }
1754 
1755 private:
1756  // Partially evaluate/pre-compute all blocks being executed in parallel by
1757  // statically generate loop indices combinations
1758  LogicalResult partialEval(PatternRewriter &rewriter,
1759  scf::ParallelOp scfParOp) const {
1760  assert(scfParOp.getLoopSteps() && "Parallel loop must have steps");
1761  auto *body = scfParOp.getBody();
1762  auto parOpIVs = scfParOp.getInductionVars();
1763  auto steps = scfParOp.getStep();
1764  auto lowerBounds = scfParOp.getLowerBound();
1765  auto upperBounds = scfParOp.getUpperBound();
1766  rewriter.setInsertionPointAfter(scfParOp);
1767  scf::ParallelOp newParOp = scfParOp.cloneWithoutRegions();
1768  auto loc = newParOp.getLoc();
1769  rewriter.insert(newParOp);
1770  OpBuilder insideBuilder(newParOp);
1771  Block *currBlock = nullptr;
1772  auto &region = newParOp.getRegion();
1773  IRMapping operandMap;
1774 
1775  // extract lower bounds, upper bounds, and steps as integer index values
1776  SmallVector<int64_t> lbVals, ubVals, stepVals;
1777  for (auto lb : lowerBounds) {
1778  auto lbOp = lb.getDefiningOp<arith::ConstantIndexOp>();
1779  assert(lbOp &&
1780  "Lower bound must be a statically computable constant index");
1781  lbVals.push_back(lbOp.value());
1782  }
1783  for (auto ub : upperBounds) {
1784  auto ubOp = ub.getDefiningOp<arith::ConstantIndexOp>();
1785  assert(ubOp &&
1786  "Upper bound must be a statically computable constant index");
1787  ubVals.push_back(ubOp.value());
1788  }
1789  for (auto step : steps) {
1790  auto stepOp = step.getDefiningOp<arith::ConstantIndexOp>();
1791  assert(stepOp && "Step must be a statically computable constant index");
1792  stepVals.push_back(stepOp.value());
1793  }
1794 
1795  // Initialize indices with lower bounds
1796  SmallVector<int64_t> indices = lbVals;
1797 
1798  while (true) {
1799  // Create a new block in the region for the current combination of indices
1800  currBlock = &region.emplaceBlock();
1801  insideBuilder.setInsertionPointToEnd(currBlock);
1802 
1803  // Map induction variables to constant indices
1804  for (unsigned i = 0; i < indices.size(); ++i) {
1805  Value ivConstant =
1806  insideBuilder.create<arith::ConstantIndexOp>(loc, indices[i]);
1807  operandMap.map(parOpIVs[i], ivConstant);
1808  }
1809 
1810  for (auto it = body->begin(); it != std::prev(body->end()); ++it)
1811  insideBuilder.clone(*it, operandMap);
1812 
1813  // Increment indices using `step`
1814  bool done = false;
1815  for (int dim = indices.size() - 1; dim >= 0; --dim) {
1816  indices[dim] += stepVals[dim];
1817  if (indices[dim] < ubVals[dim])
1818  break;
1819  indices[dim] = lbVals[dim];
1820  if (dim == 0)
1821  // All combinations have been generated
1822  done = true;
1823  }
1824  if (done)
1825  break;
1826  }
1827 
1828  rewriter.replaceOp(scfParOp, newParOp);
1829  return success();
1830  }
1831 };
1832 
1833 /// Builds a control schedule by traversing the CFG of the function and
1834 /// associating this with the previously created groups.
1835 /// For simplicity, the generated control flow is expanded for all possible
1836 /// paths in the input DAG. This elaborated control flow is later reduced in
1837 /// the runControlFlowSimplification passes.
1839  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1840 
1841  LogicalResult
1843  PatternRewriter &rewriter) const override {
1844  auto *entryBlock = &funcOp.getBlocks().front();
1845  rewriter.setInsertionPointToStart(
1846  getComponent().getControlOp().getBodyBlock());
1847  auto topLevelSeqOp = rewriter.create<calyx::SeqOp>(funcOp.getLoc());
1848  DenseSet<Block *> path;
1849  return buildCFGControl(path, rewriter, topLevelSeqOp.getBodyBlock(),
1850  nullptr, entryBlock);
1851  }
1852 
1853 private:
1854  /// Sequentially schedules the groups that registered themselves with
1855  /// 'block'.
1856  LogicalResult scheduleBasicBlock(PatternRewriter &rewriter,
1857  const DenseSet<Block *> &path,
1858  mlir::Block *parentCtrlBlock,
1859  mlir::Block *block) const {
1860  auto compBlockScheduleables =
1861  getState<ComponentLoweringState>().getBlockScheduleables(block);
1862  auto loc = block->front().getLoc();
1863 
1864  if (compBlockScheduleables.size() > 1 &&
1865  !isa<scf::ParallelOp>(block->getParentOp())) {
1866  auto seqOp = rewriter.create<calyx::SeqOp>(loc);
1867  parentCtrlBlock = seqOp.getBodyBlock();
1868  }
1869 
1870  for (auto &group : compBlockScheduleables) {
1871  rewriter.setInsertionPointToEnd(parentCtrlBlock);
1872  if (auto groupPtr = std::get_if<calyx::GroupOp>(&group); groupPtr) {
1873  rewriter.create<calyx::EnableOp>(groupPtr->getLoc(),
1874  groupPtr->getSymName());
1875  } else if (auto whileSchedPtr = std::get_if<WhileScheduleable>(&group);
1876  whileSchedPtr) {
1877  auto &whileOp = whileSchedPtr->whileOp;
1878 
1879  auto whileCtrlOp = buildWhileCtrlOp(
1880  whileOp,
1881  getState<ComponentLoweringState>().getWhileLoopInitGroups(whileOp),
1882  rewriter);
1883  rewriter.setInsertionPointToEnd(whileCtrlOp.getBodyBlock());
1884  auto whileBodyOp =
1885  rewriter.create<calyx::SeqOp>(whileOp.getOperation()->getLoc());
1886  auto *whileBodyOpBlock = whileBodyOp.getBodyBlock();
1887 
1888  /// Only schedule the 'after' block. The 'before' block is
1889  /// implicitly scheduled when evaluating the while condition.
1890  if (LogicalResult result =
1891  buildCFGControl(path, rewriter, whileBodyOpBlock, block,
1892  whileOp.getBodyBlock());
1893  result.failed())
1894  return result;
1895 
1896  // Insert loop-latch at the end of the while group
1897  rewriter.setInsertionPointToEnd(whileBodyOpBlock);
1898  calyx::GroupOp whileLatchGroup =
1899  getState<ComponentLoweringState>().getWhileLoopLatchGroup(whileOp);
1900  rewriter.create<calyx::EnableOp>(whileLatchGroup.getLoc(),
1901  whileLatchGroup.getName());
1902  } else if (auto *parSchedPtr = std::get_if<ParScheduleable>(&group)) {
1903  auto parOp = parSchedPtr->parOp;
1904  auto calyxParOp = rewriter.create<calyx::ParOp>(parOp.getLoc());
1905  for (auto &innerBlock : parOp.getRegion().getBlocks()) {
1906  rewriter.setInsertionPointToEnd(calyxParOp.getBodyBlock());
1907  auto seqOp = rewriter.create<calyx::SeqOp>(parOp.getLoc());
1908  rewriter.setInsertionPointToEnd(seqOp.getBodyBlock());
1909  if (LogicalResult res = scheduleBasicBlock(
1910  rewriter, path, seqOp.getBodyBlock(), &innerBlock);
1911  res.failed())
1912  return res;
1913  }
1914  } else if (auto *forSchedPtr = std::get_if<ForScheduleable>(&group);
1915  forSchedPtr) {
1916  auto forOp = forSchedPtr->forOp;
1917 
1918  auto forCtrlOp = buildForCtrlOp(
1919  forOp,
1920  getState<ComponentLoweringState>().getForLoopInitGroups(forOp),
1921  forSchedPtr->bound, rewriter);
1922  rewriter.setInsertionPointToEnd(forCtrlOp.getBodyBlock());
1923  auto forBodyOp =
1924  rewriter.create<calyx::SeqOp>(forOp.getOperation()->getLoc());
1925  auto *forBodyOpBlock = forBodyOp.getBodyBlock();
1926 
1927  // Schedule the body of the for loop.
1928  if (LogicalResult res = buildCFGControl(path, rewriter, forBodyOpBlock,
1929  block, forOp.getBodyBlock());
1930  res.failed())
1931  return res;
1932 
1933  // Insert loop-latch at the end of the while group.
1934  rewriter.setInsertionPointToEnd(forBodyOpBlock);
1935  calyx::GroupOp forLatchGroup =
1936  getState<ComponentLoweringState>().getForLoopLatchGroup(forOp);
1937  rewriter.create<calyx::EnableOp>(forLatchGroup.getLoc(),
1938  forLatchGroup.getName());
1939  } else if (auto *ifSchedPtr = std::get_if<IfScheduleable>(&group);
1940  ifSchedPtr) {
1941  auto ifOp = ifSchedPtr->ifOp;
1942 
1943  Location loc = ifOp->getLoc();
1944 
1945  auto cond = ifOp.getCondition();
1946  auto condGroup = getState<ComponentLoweringState>()
1947  .getEvaluatingGroup<calyx::CombGroupOp>(cond);
1948 
1949  auto symbolAttr = FlatSymbolRefAttr::get(
1950  StringAttr::get(getContext(), condGroup.getSymName()));
1951 
1952  bool initElse = !ifOp.getElseRegion().empty();
1953  auto ifCtrlOp = rewriter.create<calyx::IfOp>(
1954  loc, cond, symbolAttr, /*initializeElseBody=*/initElse);
1955 
1956  rewriter.setInsertionPointToEnd(ifCtrlOp.getBodyBlock());
1957 
1958  auto thenSeqOp =
1959  rewriter.create<calyx::SeqOp>(ifOp.getThenRegion().getLoc());
1960  auto *thenSeqOpBlock = thenSeqOp.getBodyBlock();
1961 
1962  auto *thenBlock = &ifOp.getThenRegion().front();
1963  LogicalResult res = buildCFGControl(path, rewriter, thenSeqOpBlock,
1964  /*preBlock=*/block, thenBlock);
1965  if (res.failed())
1966  return res;
1967 
1968  rewriter.setInsertionPointToEnd(thenSeqOpBlock);
1969  calyx::GroupOp thenGroup =
1970  getState<ComponentLoweringState>().getThenGroup(ifOp);
1971  rewriter.create<calyx::EnableOp>(thenGroup.getLoc(),
1972  thenGroup.getName());
1973 
1974  if (!ifOp.getElseRegion().empty()) {
1975  rewriter.setInsertionPointToEnd(ifCtrlOp.getElseBody());
1976 
1977  auto elseSeqOp =
1978  rewriter.create<calyx::SeqOp>(ifOp.getElseRegion().getLoc());
1979  auto *elseSeqOpBlock = elseSeqOp.getBodyBlock();
1980 
1981  auto *elseBlock = &ifOp.getElseRegion().front();
1982  res = buildCFGControl(path, rewriter, elseSeqOpBlock,
1983  /*preBlock=*/block, elseBlock);
1984  if (res.failed())
1985  return res;
1986 
1987  rewriter.setInsertionPointToEnd(elseSeqOpBlock);
1988  calyx::GroupOp elseGroup =
1989  getState<ComponentLoweringState>().getElseGroup(ifOp);
1990  rewriter.create<calyx::EnableOp>(elseGroup.getLoc(),
1991  elseGroup.getName());
1992  }
1993  } else if (auto *callSchedPtr = std::get_if<CallScheduleable>(&group)) {
1994  auto instanceOp = callSchedPtr->instanceOp;
1995  OpBuilder::InsertionGuard g(rewriter);
1996  auto callBody = rewriter.create<calyx::SeqOp>(instanceOp.getLoc());
1997  rewriter.setInsertionPointToStart(callBody.getBodyBlock());
1998  std::string initGroupName = "init_" + instanceOp.getSymName().str();
1999  rewriter.create<calyx::EnableOp>(instanceOp.getLoc(), initGroupName);
2000 
2001  auto callee = callSchedPtr->callOp.getCallee();
2002  auto *calleeOp = SymbolTable::lookupNearestSymbolFrom(
2003  callSchedPtr->callOp.getOperation()->getParentOp(),
2004  StringAttr::get(rewriter.getContext(), "func_" + callee.str()));
2005  FuncOp calleeFunc = dyn_cast_or_null<FuncOp>(calleeOp);
2006 
2007  auto instanceOpComp =
2008  llvm::cast<calyx::ComponentOp>(instanceOp.getReferencedComponent());
2009  auto *instanceOpLoweringState =
2010  loweringState().getState(instanceOpComp);
2011 
2012  SmallVector<Value, 4> instancePorts;
2013  SmallVector<Value, 4> inputPorts;
2014  SmallVector<Attribute, 4> refCells;
2015  for (auto operandEnum : enumerate(callSchedPtr->callOp.getOperands())) {
2016  auto operand = operandEnum.value();
2017  auto index = operandEnum.index();
2018  if (!isa<MemRefType>(operand.getType())) {
2019  inputPorts.push_back(operand);
2020  continue;
2021  }
2022 
2023  auto memOpName = getState<ComponentLoweringState>()
2024  .getMemoryInterface(operand)
2025  .memName();
2026  auto memOpNameAttr =
2027  SymbolRefAttr::get(rewriter.getContext(), memOpName);
2028  Value argI = calleeFunc.getArgument(index);
2029  if (isa<MemRefType>(argI.getType())) {
2030  NamedAttrList namedAttrList;
2031  namedAttrList.append(
2032  rewriter.getStringAttr(
2033  instanceOpLoweringState->getMemoryInterface(argI)
2034  .memName()),
2035  memOpNameAttr);
2036  refCells.push_back(
2037  DictionaryAttr::get(rewriter.getContext(), namedAttrList));
2038  }
2039  }
2040  llvm::copy(instanceOp.getResults().take_front(inputPorts.size()),
2041  std::back_inserter(instancePorts));
2042 
2043  ArrayAttr refCellsAttr =
2044  ArrayAttr::get(rewriter.getContext(), refCells);
2045 
2046  rewriter.create<calyx::InvokeOp>(
2047  instanceOp.getLoc(), instanceOp.getSymName(), instancePorts,
2048  inputPorts, refCellsAttr, ArrayAttr::get(rewriter.getContext(), {}),
2049  ArrayAttr::get(rewriter.getContext(), {}));
2050  } else
2051  llvm_unreachable("Unknown scheduleable");
2052  }
2053  return success();
2054  }
2055 
2056  /// Schedules a block by inserting a branch argument assignment block (if any)
2057  /// before recursing into the scheduling of the block innards.
2058  /// Blocks 'from' and 'to' refer to blocks in the source program.
2059  /// parentCtrlBlock refers to the control block wherein control operations are
2060  /// to be inserted.
2061  LogicalResult schedulePath(PatternRewriter &rewriter,
2062  const DenseSet<Block *> &path, Location loc,
2063  Block *from, Block *to,
2064  Block *parentCtrlBlock) const {
2065  /// Schedule any registered block arguments to be executed before the body
2066  /// of the branch.
2067  rewriter.setInsertionPointToEnd(parentCtrlBlock);
2068  auto preSeqOp = rewriter.create<calyx::SeqOp>(loc);
2069  rewriter.setInsertionPointToEnd(preSeqOp.getBodyBlock());
2070  for (auto barg :
2071  getState<ComponentLoweringState>().getBlockArgGroups(from, to))
2072  rewriter.create<calyx::EnableOp>(barg.getLoc(), barg.getSymName());
2073 
2074  return buildCFGControl(path, rewriter, parentCtrlBlock, from, to);
2075  }
2076 
2077  LogicalResult buildCFGControl(DenseSet<Block *> path,
2078  PatternRewriter &rewriter,
2079  mlir::Block *parentCtrlBlock,
2080  mlir::Block *preBlock,
2081  mlir::Block *block) const {
2082  if (path.count(block) != 0)
2083  return preBlock->getTerminator()->emitError()
2084  << "CFG backedge detected. Loops must be raised to 'scf.while' or "
2085  "'scf.for' operations.";
2086 
2087  rewriter.setInsertionPointToEnd(parentCtrlBlock);
2088  LogicalResult bbSchedResult =
2089  scheduleBasicBlock(rewriter, path, parentCtrlBlock, block);
2090  if (bbSchedResult.failed())
2091  return bbSchedResult;
2092 
2093  path.insert(block);
2094  auto successors = block->getSuccessors();
2095  auto nSuccessors = successors.size();
2096  if (nSuccessors > 0) {
2097  auto brOp = dyn_cast<BranchOpInterface>(block->getTerminator());
2098  assert(brOp);
2099  if (nSuccessors > 1) {
2100  /// TODO(mortbopet): we could choose to support ie. std.switch, but it
2101  /// would probably be easier to just require it to be lowered
2102  /// beforehand.
2103  assert(nSuccessors == 2 &&
2104  "only conditional branches supported for now...");
2105  /// Wrap each branch inside an if/else.
2106  auto cond = brOp->getOperand(0);
2107  auto condGroup = getState<ComponentLoweringState>()
2108  .getEvaluatingGroup<calyx::CombGroupOp>(cond);
2109  auto symbolAttr = FlatSymbolRefAttr::get(
2110  StringAttr::get(getContext(), condGroup.getSymName()));
2111 
2112  auto ifOp = rewriter.create<calyx::IfOp>(
2113  brOp->getLoc(), cond, symbolAttr, /*initializeElseBody=*/true);
2114  rewriter.setInsertionPointToStart(ifOp.getThenBody());
2115  auto thenSeqOp = rewriter.create<calyx::SeqOp>(brOp.getLoc());
2116  rewriter.setInsertionPointToStart(ifOp.getElseBody());
2117  auto elseSeqOp = rewriter.create<calyx::SeqOp>(brOp.getLoc());
2118 
2119  bool trueBrSchedSuccess =
2120  schedulePath(rewriter, path, brOp.getLoc(), block, successors[0],
2121  thenSeqOp.getBodyBlock())
2122  .succeeded();
2123  bool falseBrSchedSuccess = true;
2124  if (trueBrSchedSuccess) {
2125  falseBrSchedSuccess =
2126  schedulePath(rewriter, path, brOp.getLoc(), block, successors[1],
2127  elseSeqOp.getBodyBlock())
2128  .succeeded();
2129  }
2130 
2131  return success(trueBrSchedSuccess && falseBrSchedSuccess);
2132  } else {
2133  /// Schedule sequentially within the current parent control block.
2134  return schedulePath(rewriter, path, brOp.getLoc(), block,
2135  successors.front(), parentCtrlBlock);
2136  }
2137  }
2138  return success();
2139  }
2140 
2141  // Insert a Par of initGroups at Location loc. Used as helper for
2142  // `buildWhileCtrlOp` and `buildForCtrlOp`.
2143  void
2144  insertParInitGroups(PatternRewriter &rewriter, Location loc,
2145  const SmallVector<calyx::GroupOp> &initGroups) const {
2146  PatternRewriter::InsertionGuard g(rewriter);
2147  auto parOp = rewriter.create<calyx::ParOp>(loc);
2148  rewriter.setInsertionPointToStart(parOp.getBodyBlock());
2149  for (calyx::GroupOp group : initGroups)
2150  rewriter.create<calyx::EnableOp>(group.getLoc(), group.getName());
2151  }
2152 
2153  calyx::WhileOp buildWhileCtrlOp(ScfWhileOp whileOp,
2154  SmallVector<calyx::GroupOp> initGroups,
2155  PatternRewriter &rewriter) const {
2156  Location loc = whileOp.getLoc();
2157  /// Insert while iter arg initialization group(s). Emit a
2158  /// parallel group to assign one or more registers all at once.
2159  insertParInitGroups(rewriter, loc, initGroups);
2160 
2161  /// Insert the while op itself.
2162  auto cond = whileOp.getConditionValue();
2163  auto condGroup = getState<ComponentLoweringState>()
2164  .getEvaluatingGroup<calyx::CombGroupOp>(cond);
2165  auto symbolAttr = FlatSymbolRefAttr::get(
2166  StringAttr::get(getContext(), condGroup.getSymName()));
2167  return rewriter.create<calyx::WhileOp>(loc, cond, symbolAttr);
2168  }
2169 
2170  calyx::RepeatOp buildForCtrlOp(ScfForOp forOp,
2171  SmallVector<calyx::GroupOp> const &initGroups,
2172  uint64_t bound,
2173  PatternRewriter &rewriter) const {
2174  Location loc = forOp.getLoc();
2175  // Insert for iter arg initialization group(s). Emit a
2176  // parallel group to assign one or more registers all at once.
2177  insertParInitGroups(rewriter, loc, initGroups);
2178 
2179  // Insert the repeatOp that corresponds to the For loop.
2180  return rewriter.create<calyx::RepeatOp>(loc, bound);
2181  }
2182 };
2183 
2184 /// LateSSAReplacement contains various functions for replacing SSA values that
2185 /// were not replaced during op construction.
2187  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
2188 
2189  LogicalResult partiallyLowerFuncToComp(FuncOp funcOp,
2190  PatternRewriter &) const override {
2191  funcOp.walk([&](scf::IfOp op) {
2192  for (auto res : getState<ComponentLoweringState>().getResultRegs(op))
2193  op.getOperation()->getResults()[res.first].replaceAllUsesWith(
2194  res.second.getOut());
2195  });
2196 
2197  funcOp.walk([&](scf::WhileOp op) {
2198  /// The yielded values returned from the while op will be present in the
2199  /// iterargs registers post execution of the loop.
2200  /// This is done now, as opposed to during BuildWhileGroups since if the
2201  /// results of the whileOp were replaced before
2202  /// BuildOpGroups/BuildControl, the whileOp would get dead-code
2203  /// eliminated.
2204  ScfWhileOp whileOp(op);
2205  for (auto res :
2206  getState<ComponentLoweringState>().getWhileLoopIterRegs(whileOp))
2207  whileOp.getOperation()->getResults()[res.first].replaceAllUsesWith(
2208  res.second.getOut());
2209  });
2210 
2211  funcOp.walk([&](memref::LoadOp loadOp) {
2212  if (calyx::singleLoadFromMemory(loadOp)) {
2213  /// In buildOpGroups we did not replace loadOp's results, to ensure a
2214  /// link between evaluating groups (which fix the input addresses of a
2215  /// memory op) and a readData result. Now, we may replace these SSA
2216  /// values with their memoryOp readData output.
2217  loadOp.getResult().replaceAllUsesWith(
2218  getState<ComponentLoweringState>()
2219  .getMemoryInterface(loadOp.getMemref())
2220  .readData());
2221  }
2222  });
2223 
2224  return success();
2225  }
2226 };
2227 
2228 /// Erases FuncOp operations.
2230  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
2231 
2232  LogicalResult matchAndRewrite(FuncOp funcOp,
2233  PatternRewriter &rewriter) const override {
2234  rewriter.eraseOp(funcOp);
2235  return success();
2236  }
2237 
2238  LogicalResult
2240  PatternRewriter &rewriter) const override {
2241  return success();
2242  }
2243 };
2244 
2245 } // namespace scftocalyx
2246 
2247 namespace {
2248 
2249 using namespace circt::scftocalyx;
2250 
2251 //===----------------------------------------------------------------------===//
2252 // Pass driver
2253 //===----------------------------------------------------------------------===//
2254 class SCFToCalyxPass : public circt::impl::SCFToCalyxBase<SCFToCalyxPass> {
2255 public:
2256  SCFToCalyxPass()
2257  : SCFToCalyxBase<SCFToCalyxPass>(), partialPatternRes(success()) {}
2258  void runOnOperation() override;
2259 
2260  LogicalResult setTopLevelFunction(mlir::ModuleOp moduleOp,
2261  std::string &topLevelFunction) {
2262  if (!topLevelFunctionOpt.empty()) {
2263  if (SymbolTable::lookupSymbolIn(moduleOp, topLevelFunctionOpt) ==
2264  nullptr) {
2265  moduleOp.emitError() << "Top level function '" << topLevelFunctionOpt
2266  << "' not found in module.";
2267  return failure();
2268  }
2269  topLevelFunction = topLevelFunctionOpt;
2270  } else {
2271  /// No top level function set; infer top level if the module only contains
2272  /// a single function, else, throw error.
2273  auto funcOps = moduleOp.getOps<FuncOp>();
2274  if (std::distance(funcOps.begin(), funcOps.end()) == 1)
2275  topLevelFunction = (*funcOps.begin()).getSymName().str();
2276  else {
2277  moduleOp.emitError()
2278  << "Module contains multiple functions, but no top level "
2279  "function was set. Please see --top-level-function";
2280  return failure();
2281  }
2282  }
2283 
2284  return createOptNewTopLevelFn(moduleOp, topLevelFunction);
2285  }
2286 
2287  struct LoweringPattern {
2288  enum class Strategy { Once, Greedy };
2289  RewritePatternSet pattern;
2290  Strategy strategy;
2291  };
2292 
2293  //// Labels the entry point of a Calyx program.
2294  /// Furthermore, this function performs validation on the input function,
2295  /// to ensure that we've implemented the capabilities necessary to convert
2296  /// it.
2297  LogicalResult labelEntryPoint(StringRef topLevelFunction) {
2298  // Program legalization - the partial conversion driver will not run
2299  // unless some pattern is provided - provide a dummy pattern.
2300  struct DummyPattern : public OpRewritePattern<mlir::ModuleOp> {
2301  using OpRewritePattern::OpRewritePattern;
2302  LogicalResult matchAndRewrite(mlir::ModuleOp,
2303  PatternRewriter &) const override {
2304  return failure();
2305  }
2306  };
2307 
2308  ConversionTarget target(getContext());
2309  target.addLegalDialect<calyx::CalyxDialect>();
2310  target.addLegalDialect<scf::SCFDialect>();
2311  target.addIllegalDialect<hw::HWDialect>();
2312  target.addIllegalDialect<comb::CombDialect>();
2313 
2314  // Only accept std operations which we've added lowerings for
2315  target.addIllegalDialect<FuncDialect>();
2316  target.addIllegalDialect<ArithDialect>();
2317  target.addLegalOp<AddIOp, SelectOp, SubIOp, CmpIOp, ShLIOp, ShRUIOp,
2318  ShRSIOp, AndIOp, XOrIOp, OrIOp, ExtUIOp, TruncIOp,
2319  CondBranchOp, BranchOp, MulIOp, DivUIOp, DivSIOp, RemUIOp,
2320  RemSIOp, ReturnOp, arith::ConstantOp, IndexCastOp, FuncOp,
2321  ExtSIOp, CallOp, AddFOp, MulFOp, CmpFOp>();
2322 
2323  RewritePatternSet legalizePatterns(&getContext());
2324  legalizePatterns.add<DummyPattern>(&getContext());
2325  DenseSet<Operation *> legalizedOps;
2326  if (applyPartialConversion(getOperation(), target,
2327  std::move(legalizePatterns))
2328  .failed())
2329  return failure();
2330 
2331  // Program conversion
2332  return calyx::applyModuleOpConversion(getOperation(), topLevelFunction);
2333  }
2334 
2335  /// 'Once' patterns are expected to take an additional LogicalResult&
2336  /// argument, to forward their result state (greedyPatternRewriteDriver
2337  /// results are skipped for Once patterns).
2338  template <typename TPattern, typename... PatternArgs>
2339  void addOncePattern(SmallVectorImpl<LoweringPattern> &patterns,
2340  PatternArgs &&...args) {
2341  RewritePatternSet ps(&getContext());
2342  ps.add<TPattern>(&getContext(), partialPatternRes, args...);
2343  patterns.push_back(
2344  LoweringPattern{std::move(ps), LoweringPattern::Strategy::Once});
2345  }
2346 
2347  template <typename TPattern, typename... PatternArgs>
2348  void addGreedyPattern(SmallVectorImpl<LoweringPattern> &patterns,
2349  PatternArgs &&...args) {
2350  RewritePatternSet ps(&getContext());
2351  ps.add<TPattern>(&getContext(), args...);
2352  patterns.push_back(
2353  LoweringPattern{std::move(ps), LoweringPattern::Strategy::Greedy});
2354  }
2355 
2356  LogicalResult runPartialPattern(RewritePatternSet &pattern, bool runOnce) {
2357  assert(pattern.getNativePatterns().size() == 1 &&
2358  "Should only apply 1 partial lowering pattern at once");
2359 
2360  // During component creation, the function body is inlined into the
2361  // component body for further processing. However, proper control flow
2362  // will only be established later in the conversion process, so ensure
2363  // that rewriter optimizations (especially DCE) are disabled.
2364  GreedyRewriteConfig config;
2365  config.enableRegionSimplification =
2366  mlir::GreedySimplifyRegionLevel::Disabled;
2367  if (runOnce)
2368  config.maxIterations = 1;
2369 
2370  /// Can't return applyPatternsAndFoldGreedily. Root isn't
2371  /// necessarily erased so it will always return failed(). Instead,
2372  /// forward the 'succeeded' value from PartialLoweringPatternBase.
2373  (void)applyPatternsAndFoldGreedily(getOperation(), std::move(pattern),
2374  config);
2375  return partialPatternRes;
2376  }
2377 
2378 private:
2379  LogicalResult partialPatternRes;
2380  std::shared_ptr<calyx::CalyxLoweringState> loweringState = nullptr;
2381 
2382  /// Creates a new new top-level function based on `baseName`.
2383  FuncOp createNewTopLevelFn(ModuleOp moduleOp, std::string &baseName) {
2384  std::string newName = "main";
2385 
2386  if (auto *existingMainOp = SymbolTable::lookupSymbolIn(moduleOp, newName)) {
2387  auto existingMainFunc = dyn_cast<FuncOp>(existingMainOp);
2388  if (existingMainFunc == nullptr) {
2389  moduleOp.emitError() << "Symbol 'main' exists but is not a function";
2390  return nullptr;
2391  }
2392  unsigned counter = 0;
2393  std::string newOldName = baseName;
2394  while (SymbolTable::lookupSymbolIn(moduleOp, newOldName))
2395  newOldName = llvm::join_items("_", baseName, std::to_string(++counter));
2396  existingMainFunc.setName(newOldName);
2397  if (baseName == "main")
2398  baseName = newOldName;
2399  }
2400 
2401  // Create the new "main" function
2402  OpBuilder builder(moduleOp.getContext());
2403  builder.setInsertionPointToStart(moduleOp.getBody());
2404 
2405  FunctionType funcType = builder.getFunctionType({}, {});
2406 
2407  if (auto newFunc =
2408  builder.create<FuncOp>(moduleOp.getLoc(), newName, funcType))
2409  return newFunc;
2410 
2411  return nullptr;
2412  }
2413 
2414  /// Insert a call from the newly created top-level function/`caller` to the
2415  /// old top-level function/`callee`; and create `memref.alloc`s inside the new
2416  /// top-level function for arguments with `memref` types and for the
2417  /// `memref.alloc`s inside `callee`.
2418  void insertCallFromNewTopLevel(OpBuilder &builder, FuncOp caller,
2419  FuncOp callee) {
2420  if (caller.getBody().empty()) {
2421  caller.addEntryBlock();
2422  }
2423 
2424  Block *callerEntryBlock = &caller.getBody().front();
2425  builder.setInsertionPointToStart(callerEntryBlock);
2426 
2427  // For those non-memref arguments passing to the original top-level
2428  // function, we need to copy them to the new top-level function.
2429  SmallVector<Type, 4> nonMemRefCalleeArgTypes;
2430  for (auto arg : callee.getArguments()) {
2431  if (!isa<MemRefType>(arg.getType())) {
2432  nonMemRefCalleeArgTypes.push_back(arg.getType());
2433  }
2434  }
2435 
2436  for (Type type : nonMemRefCalleeArgTypes) {
2437  callerEntryBlock->addArgument(type, caller.getLoc());
2438  }
2439 
2440  FunctionType callerFnType = caller.getFunctionType();
2441  SmallVector<Type, 4> updatedCallerArgTypes(
2442  caller.getFunctionType().getInputs());
2443  updatedCallerArgTypes.append(nonMemRefCalleeArgTypes.begin(),
2444  nonMemRefCalleeArgTypes.end());
2445  caller.setType(FunctionType::get(caller.getContext(), updatedCallerArgTypes,
2446  callerFnType.getResults()));
2447 
2448  Block *calleeFnBody = &callee.getBody().front();
2449  unsigned originalCalleeArgNum = callee.getArguments().size();
2450 
2451  SmallVector<Value, 4> extraMemRefArgs;
2452  SmallVector<Type, 4> extraMemRefArgTypes;
2453  SmallVector<Value, 4> extraMemRefOperands;
2454  SmallVector<Operation *, 4> opsToModify;
2455  for (auto &op : callee.getBody().getOps()) {
2456  if (isa<memref::AllocaOp, memref::AllocOp, memref::GetGlobalOp>(op))
2457  opsToModify.push_back(&op);
2458  }
2459 
2460  // Replace `alloc`/`getGlobal` in the original top-level with new
2461  // corresponding operations in the new top-level.
2462  builder.setInsertionPointToEnd(callerEntryBlock);
2463  for (auto *op : opsToModify) {
2464  // TODO (https://github.com/llvm/circt/issues/7764)
2465  Value newOpRes;
2466  TypeSwitch<Operation *>(op)
2467  .Case<memref::AllocaOp>([&](memref::AllocaOp allocaOp) {
2468  newOpRes = builder.create<memref::AllocaOp>(callee.getLoc(),
2469  allocaOp.getType());
2470  })
2471  .Case<memref::AllocOp>([&](memref::AllocOp allocOp) {
2472  newOpRes = builder.create<memref::AllocOp>(callee.getLoc(),
2473  allocOp.getType());
2474  })
2475  .Case<memref::GetGlobalOp>([&](memref::GetGlobalOp getGlobalOp) {
2476  newOpRes = builder.create<memref::GetGlobalOp>(
2477  caller.getLoc(), getGlobalOp.getType(), getGlobalOp.getName());
2478  })
2479  .Default([&](Operation *defaultOp) {
2480  llvm::report_fatal_error("Unsupported operation in TypeSwitch");
2481  });
2482  extraMemRefOperands.push_back(newOpRes);
2483 
2484  calleeFnBody->addArgument(newOpRes.getType(), callee.getLoc());
2485  BlockArgument newBodyArg = calleeFnBody->getArguments().back();
2486  op->getResult(0).replaceAllUsesWith(newBodyArg);
2487  op->erase();
2488  extraMemRefArgs.push_back(newBodyArg);
2489  extraMemRefArgTypes.push_back(newBodyArg.getType());
2490  }
2491 
2492  SmallVector<Type, 4> updatedCalleeArgTypes(
2493  callee.getFunctionType().getInputs());
2494  updatedCalleeArgTypes.append(extraMemRefArgTypes.begin(),
2495  extraMemRefArgTypes.end());
2496  callee.setType(FunctionType::get(callee.getContext(), updatedCalleeArgTypes,
2497  callee.getFunctionType().getResults()));
2498 
2499  unsigned otherArgsCount = 0;
2500  SmallVector<Value, 4> calleeArgFnOperands;
2501  builder.setInsertionPointToStart(callerEntryBlock);
2502  for (auto arg : callee.getArguments().take_front(originalCalleeArgNum)) {
2503  if (isa<MemRefType>(arg.getType())) {
2504  auto memrefType = cast<MemRefType>(arg.getType());
2505  auto allocOp =
2506  builder.create<memref::AllocOp>(callee.getLoc(), memrefType);
2507  calleeArgFnOperands.push_back(allocOp);
2508  } else {
2509  auto callerArg = callerEntryBlock->getArgument(otherArgsCount++);
2510  calleeArgFnOperands.push_back(callerArg);
2511  }
2512  }
2513 
2514  SmallVector<Value, 4> fnOperands;
2515  fnOperands.append(calleeArgFnOperands.begin(), calleeArgFnOperands.end());
2516  fnOperands.append(extraMemRefOperands.begin(), extraMemRefOperands.end());
2517  auto calleeName =
2518  SymbolRefAttr::get(builder.getContext(), callee.getSymName());
2519  auto resultTypes = callee.getResultTypes();
2520 
2521  builder.setInsertionPointToEnd(callerEntryBlock);
2522  builder.create<CallOp>(caller.getLoc(), calleeName, resultTypes,
2523  fnOperands);
2524  }
2525 
2526  /// Conditionally creates an optional new top-level function; and inserts a
2527  /// call from the new top-level function to the old top-level function if we
2528  /// did create one
2529  LogicalResult createOptNewTopLevelFn(ModuleOp moduleOp,
2530  std::string &topLevelFunction) {
2531  auto hasMemrefArguments = [](FuncOp func) {
2532  return std::any_of(
2533  func.getArguments().begin(), func.getArguments().end(),
2534  [](BlockArgument arg) { return isa<MemRefType>(arg.getType()); });
2535  };
2536 
2537  /// We only create a new top-level function and call the original top-level
2538  /// function from the new one if the original top-level has `memref` in its
2539  /// argument
2540  auto funcOps = moduleOp.getOps<FuncOp>();
2541  bool hasMemrefArgsInTopLevel =
2542  std::any_of(funcOps.begin(), funcOps.end(), [&](auto funcOp) {
2543  return funcOp.getName() == topLevelFunction &&
2544  hasMemrefArguments(funcOp);
2545  });
2546 
2547  if (hasMemrefArgsInTopLevel) {
2548  auto newTopLevelFunc = createNewTopLevelFn(moduleOp, topLevelFunction);
2549  if (!newTopLevelFunc)
2550  return failure();
2551 
2552  OpBuilder builder(moduleOp.getContext());
2553  Operation *oldTopLevelFuncOp =
2554  SymbolTable::lookupSymbolIn(moduleOp, topLevelFunction);
2555  if (auto oldTopLevelFunc = dyn_cast<FuncOp>(oldTopLevelFuncOp))
2556  insertCallFromNewTopLevel(builder, newTopLevelFunc, oldTopLevelFunc);
2557  else {
2558  moduleOp.emitOpError("Original top-level function not found!");
2559  return failure();
2560  }
2561  topLevelFunction = "main";
2562  }
2563 
2564  return success();
2565  }
2566 };
2567 
2568 void SCFToCalyxPass::runOnOperation() {
2569  // Clear internal state. See https://github.com/llvm/circt/issues/3235
2570  loweringState.reset();
2571  partialPatternRes = LogicalResult::failure();
2572 
2573  std::string topLevelFunction;
2574  if (failed(setTopLevelFunction(getOperation(), topLevelFunction))) {
2575  signalPassFailure();
2576  return;
2577  }
2578 
2579  /// Start conversion
2580  if (failed(labelEntryPoint(topLevelFunction))) {
2581  signalPassFailure();
2582  return;
2583  }
2584  loweringState = std::make_shared<calyx::CalyxLoweringState>(getOperation(),
2585  topLevelFunction);
2586 
2587  /// --------------------------------------------------------------------------
2588  /// If you are a developer, it may be helpful to add a
2589  /// 'getOperation()->dump()' call after the execution of each stage to
2590  /// view the transformations that's going on.
2591  /// --------------------------------------------------------------------------
2592 
2593  /// A mapping is maintained between a function operation and its corresponding
2594  /// Calyx component.
2595  DenseMap<FuncOp, calyx::ComponentOp> funcMap;
2596  SmallVector<LoweringPattern, 8> loweringPatterns;
2597  calyx::PatternApplicationState patternState;
2598 
2599  /// Creates a new Calyx component for each FuncOp in the inpurt module.
2600  addOncePattern<FuncOpConversion>(loweringPatterns, patternState, funcMap,
2601  *loweringState);
2602 
2603  /// This pass inlines scf.ExecuteRegionOp's by adding control-flow.
2604  addGreedyPattern<InlineExecuteRegionOpPattern>(loweringPatterns);
2605 
2606  addOncePattern<BuildParGroups>(loweringPatterns, patternState, funcMap,
2607  *loweringState);
2608 
2609  /// This pattern converts all index typed values to an i32 integer.
2610  addOncePattern<calyx::ConvertIndexTypes>(loweringPatterns, patternState,
2611  funcMap, *loweringState);
2612 
2613  /// This pattern creates registers for all basic-block arguments.
2614  addOncePattern<calyx::BuildBasicBlockRegs>(loweringPatterns, patternState,
2615  funcMap, *loweringState);
2616 
2617  addOncePattern<calyx::BuildCallInstance>(loweringPatterns, patternState,
2618  funcMap, *loweringState);
2619 
2620  /// This pattern creates registers for the function return values.
2621  addOncePattern<calyx::BuildReturnRegs>(loweringPatterns, patternState,
2622  funcMap, *loweringState);
2623 
2624  /// This pattern creates registers for iteration arguments of scf.while
2625  /// operations. Additionally, creates a group for assigning the initial
2626  /// value of the iteration argument registers.
2627  addOncePattern<BuildWhileGroups>(loweringPatterns, patternState, funcMap,
2628  *loweringState);
2629 
2630  /// This pattern creates registers for iteration arguments of scf.for
2631  /// operations. Additionally, creates a group for assigning the initial
2632  /// value of the iteration argument registers.
2633  addOncePattern<BuildForGroups>(loweringPatterns, patternState, funcMap,
2634  *loweringState);
2635 
2636  addOncePattern<BuildIfGroups>(loweringPatterns, patternState, funcMap,
2637  *loweringState);
2638 
2639  /// This pattern converts operations within basic blocks to Calyx library
2640  /// operators. Combinational operations are assigned inside a
2641  /// calyx::CombGroupOp, and sequential inside calyx::GroupOps.
2642  /// Sequential groups are registered with the Block* of which the operation
2643  /// originated from. This is used during control schedule generation. By
2644  /// having a distinct group for each operation, groups are analogous to SSA
2645  /// values in the source program.
2646  addOncePattern<BuildOpGroups>(loweringPatterns, patternState, funcMap,
2647  *loweringState);
2648 
2649  /// This pattern traverses the CFG of the program and generates a control
2650  /// schedule based on the calyx::GroupOp's which were registered for each
2651  /// basic block in the source function.
2652  addOncePattern<BuildControl>(loweringPatterns, patternState, funcMap,
2653  *loweringState);
2654 
2655  /// This pass recursively inlines use-def chains of combinational logic (from
2656  /// non-stateful groups) into groups referenced in the control schedule.
2657  addOncePattern<calyx::InlineCombGroups>(loweringPatterns, patternState,
2658  *loweringState);
2659 
2660  /// This pattern performs various SSA replacements that must be done
2661  /// after control generation.
2662  addOncePattern<LateSSAReplacement>(loweringPatterns, patternState, funcMap,
2663  *loweringState);
2664 
2665  /// Eliminate any unused combinational groups. This is done before
2666  /// calyx::RewriteMemoryAccesses to avoid inferring slice components for
2667  /// groups that will be removed.
2668  addGreedyPattern<calyx::EliminateUnusedCombGroups>(loweringPatterns);
2669 
2670  /// This pattern rewrites accesses to memories which are too wide due to
2671  /// index types being converted to a fixed-width integer type.
2672  addOncePattern<calyx::RewriteMemoryAccesses>(loweringPatterns, patternState,
2673  *loweringState);
2674 
2675  /// This pattern removes the source FuncOp which has now been converted into
2676  /// a Calyx component.
2677  addOncePattern<CleanupFuncOps>(loweringPatterns, patternState, funcMap,
2678  *loweringState);
2679 
2680  /// Sequentially apply each lowering pattern.
2681  for (auto &pat : loweringPatterns) {
2682  LogicalResult partialPatternRes = runPartialPattern(
2683  pat.pattern,
2684  /*runOnce=*/pat.strategy == LoweringPattern::Strategy::Once);
2685  if (succeeded(partialPatternRes))
2686  continue;
2687  signalPassFailure();
2688  return;
2689  }
2690 
2691  //===--------------------------------------------------------------------===//
2692  // Cleanup patterns
2693  //===--------------------------------------------------------------------===//
2694  RewritePatternSet cleanupPatterns(&getContext());
2695  cleanupPatterns.add<calyx::MultipleGroupDonePattern,
2696  calyx::NonTerminatingGroupDonePattern>(&getContext());
2697  if (failed(applyPatternsAndFoldGreedily(getOperation(),
2698  std::move(cleanupPatterns)))) {
2699  signalPassFailure();
2700  return;
2701  }
2702 
2703  if (ciderSourceLocationMetadata) {
2704  // Debugging information for the Cider debugger.
2705  // Reference: https://docs.calyxir.org/debug/cider.html
2706  SmallVector<Attribute, 16> sourceLocations;
2707  getOperation()->walk([&](calyx::ComponentOp component) {
2708  return getCiderSourceLocationMetadata(component, sourceLocations);
2709  });
2710 
2711  MLIRContext *context = getOperation()->getContext();
2712  getOperation()->setAttr("calyx.metadata",
2713  ArrayAttr::get(context, sourceLocations));
2714  }
2715 }
2716 } // namespace
2717 
2718 //===----------------------------------------------------------------------===//
2719 // Pass initialization
2720 //===----------------------------------------------------------------------===//
2721 
2722 std::unique_ptr<OperationPass<ModuleOp>> createSCFToCalyxPass() {
2723  return std::make_unique<SCFToCalyxPass>();
2724 }
2725 
2726 } // namespace circt
assert(baseType &&"element must be base type")
int32_t width
Definition: FIRRTL.cpp:36
@ Input
Definition: HW.h:35
@ Output
Definition: HW.h:35
static Block * getBodyBlock(FModuleLike mod)
RewritePatternSet pattern
Strategy strategy
std::shared_ptr< calyx::CalyxLoweringState > loweringState
LogicalResult partialPatternRes
void setFuncOpResultMapping(const DenseMap< unsigned, unsigned > &mapping)
Assign a mapping between the source funcOp result indices and the corresponding output port indices o...
std::string getUniqueName(StringRef prefix)
Returns a unique name within compOp with the provided prefix.
void registerMemoryInterface(Value memref, const calyx::MemoryInterface &memoryInterface)
Registers a memory interface as being associated with a memory identified by 'memref'.
calyx::ComponentOp getComponentOp()
Returns the calyx::ComponentOp associated with this lowering state.
FuncOpPartialLoweringPatterns are patterns which intend to match on FuncOps and then perform their ow...
Holds common utilities used for scheduling when lowering to Calyx.
Builds a control schedule by traversing the CFG of the function and associating this with the previou...
calyx::RepeatOp buildForCtrlOp(ScfForOp forOp, SmallVector< calyx::GroupOp > const &initGroups, uint64_t bound, PatternRewriter &rewriter) const
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
LogicalResult schedulePath(PatternRewriter &rewriter, const DenseSet< Block * > &path, Location loc, Block *from, Block *to, Block *parentCtrlBlock) const
Schedules a block by inserting a branch argument assignment block (if any) before recursing into the ...
calyx::WhileOp buildWhileCtrlOp(ScfWhileOp whileOp, SmallVector< calyx::GroupOp > initGroups, PatternRewriter &rewriter) const
LogicalResult scheduleBasicBlock(PatternRewriter &rewriter, const DenseSet< Block * > &path, mlir::Block *parentCtrlBlock, mlir::Block *block) const
Sequentially schedules the groups that registered themselves with 'block'.
LogicalResult buildCFGControl(DenseSet< Block * > path, PatternRewriter &rewriter, mlir::Block *parentCtrlBlock, mlir::Block *preBlock, mlir::Block *block) const
void insertParInitGroups(PatternRewriter &rewriter, Location loc, const SmallVector< calyx::GroupOp > &initGroups) const
In BuildForGroups, a register is created for the iteration argument of the for op.
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
Iterate through the operations of a source function and instantiate components or primitives based on...
Definition: SCFToCalyx.cpp:268
TGroupOp createGroupForOp(PatternRewriter &rewriter, Operation *op) const
Creates a group named by the basic block which the input op resides in.
Definition: SCFToCalyx.cpp:409
LogicalResult buildLibraryOp(PatternRewriter &rewriter, TSrcOp op) const
buildLibraryOp which provides in- and output types based on the operands and results of the op argume...
Definition: SCFToCalyx.cpp:402
calyx::RegisterOp createSignalRegister(PatternRewriter &rewriter, Value signal, bool invert, StringRef nameSuffix, calyx::CompareFOpIEEE754 calyxCmpFOp, calyx::GroupOp group) const
Definition: SCFToCalyx.cpp:507
void assignAddressPorts(PatternRewriter &rewriter, Location loc, calyx::GroupInterface group, calyx::MemoryInterface memoryInterface, Operation::operand_range addressValues) const
Creates assignments within the provided group to the address ports of the memoryOp based on the provi...
Definition: SCFToCalyx.cpp:481
LogicalResult buildLibraryOp(PatternRewriter &rewriter, TSrcOp op, TypeRange srcTypes, TypeRange dstTypes) const
buildLibraryOp will build a TCalyxLibOp inside a TGroupOp based on the source operation TSrcOp.
Definition: SCFToCalyx.cpp:358
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
Definition: SCFToCalyx.cpp:272
LogicalResult buildLibraryBinaryPipeOp(PatternRewriter &rewriter, TSrcOp op, TOpType opPipe, Value out) const
buildLibraryBinaryPipeOp will build a TCalyxLibBinaryPipeOp, to deal with MulIOp, DivUIOp and RemUIOp...
Definition: SCFToCalyx.cpp:421
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
LogicalResult partialEval(PatternRewriter &rewriter, scf::ParallelOp scfParOp) const
In BuildWhileGroups, a register is created for each iteration argumenet of the while op.
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
Erases FuncOp operations.
LogicalResult matchAndRewrite(FuncOp funcOp, PatternRewriter &rewriter) const override
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
Handles the current state of lowering of a Calyx component.
Definition: SCFToCalyx.cpp:256
ComponentLoweringState(calyx::ComponentOp component)
Definition: SCFToCalyx.cpp:258
void setForLoopInitGroups(ScfForOp op, SmallVector< calyx::GroupOp > groups)
Definition: SCFToCalyx.cpp:244
calyx::GroupOp buildForLoopIterArgAssignments(OpBuilder &builder, ScfForOp op, calyx::ComponentOp componentOp, Twine uniqueSuffix, MutableArrayRef< OpOperand > ops)
Definition: SCFToCalyx.cpp:223
void setForLoopLatchGroup(ScfForOp op, calyx::GroupOp group)
Definition: SCFToCalyx.cpp:238
SmallVector< calyx::GroupOp > getForLoopInitGroups(ScfForOp op)
Definition: SCFToCalyx.cpp:220
void addForLoopIterReg(ScfForOp op, calyx::RegisterOp reg, unsigned idx)
Definition: SCFToCalyx.cpp:229
calyx::GroupOp getForLoopLatchGroup(ScfForOp op)
Definition: SCFToCalyx.cpp:241
calyx::RegisterOp getForLoopIterReg(ScfForOp op, unsigned idx)
Definition: SCFToCalyx.cpp:235
const DenseMap< unsigned, calyx::RegisterOp > & getForLoopIterRegs(ScfForOp op)
Definition: SCFToCalyx.cpp:232
const DenseMap< unsigned, calyx::RegisterOp > & getResultRegs(scf::IfOp op)
Definition: SCFToCalyx.cpp:169
DenseMap< Operation *, calyx::GroupOp > elseGroup
Definition: SCFToCalyx.cpp:182
DenseMap< Operation *, calyx::GroupOp > thenGroup
Definition: SCFToCalyx.cpp:181
void setElseGroup(scf::IfOp op, calyx::GroupOp group)
Definition: SCFToCalyx.cpp:148
void setResultRegs(scf::IfOp op, calyx::RegisterOp reg, unsigned idx)
Definition: SCFToCalyx.cpp:162
void setThenGroup(scf::IfOp op, calyx::GroupOp group)
Definition: SCFToCalyx.cpp:134
DenseMap< Operation *, DenseMap< unsigned, calyx::RegisterOp > > resultRegs
Definition: SCFToCalyx.cpp:183
calyx::RegisterOp getResultRegs(scf::IfOp op, unsigned idx)
Definition: SCFToCalyx.cpp:173
calyx::GroupOp getThenGroup(scf::IfOp op)
Definition: SCFToCalyx.cpp:141
calyx::GroupOp getElseGroup(scf::IfOp op)
Definition: SCFToCalyx.cpp:155
Inlines Calyx ExecuteRegionOp operations within their parent blocks.
LogicalResult matchAndRewrite(scf::ExecuteRegionOp execOp, PatternRewriter &rewriter) const override
LateSSAReplacement contains various functions for replacing SSA values that were not replaced during ...
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &) const override
std::optional< int64_t > getBound() override
Definition: SCFToCalyx.cpp:88
Block * getBodyBlock() override
Definition: SCFToCalyx.cpp:84
Block::BlockArgListType getBodyArgs() override
Definition: SCFToCalyx.cpp:80
ScfWhileOp(scf::WhileOp op)
Definition: SCFToCalyx.cpp:56
Block::BlockArgListType getBodyArgs() override
Definition: SCFToCalyx.cpp:59
Block * getConditionBlock() override
Definition: SCFToCalyx.cpp:65
std::optional< int64_t > getBound() override
Definition: SCFToCalyx.cpp:73
Block * getBodyBlock() override
Definition: SCFToCalyx.cpp:63
Value getConditionValue() override
Definition: SCFToCalyx.cpp:69
calyx::GroupOp buildWhileLoopIterArgAssignments(OpBuilder &builder, ScfWhileOp op, calyx::ComponentOp componentOp, Twine uniqueSuffix, MutableArrayRef< OpOperand > ops)
Definition: SCFToCalyx.cpp:192
void setWhileLoopInitGroups(ScfWhileOp op, SmallVector< calyx::GroupOp > groups)
Definition: SCFToCalyx.cpp:211
SmallVector< calyx::GroupOp > getWhileLoopInitGroups(ScfWhileOp op)
Definition: SCFToCalyx.cpp:189
void addWhileLoopIterReg(ScfWhileOp op, calyx::RegisterOp reg, unsigned idx)
Definition: SCFToCalyx.cpp:198
const DenseMap< unsigned, calyx::RegisterOp > & getWhileLoopIterRegs(ScfWhileOp op)
Definition: SCFToCalyx.cpp:202
void setWhileLoopLatchGroup(ScfWhileOp op, calyx::GroupOp group)
Definition: SCFToCalyx.cpp:205
calyx::GroupOp getWhileLoopLatchGroup(ScfWhileOp op)
Definition: SCFToCalyx.cpp:208
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition: CalyxOps.cpp:55
void addMandatoryComponentPorts(PatternRewriter &rewriter, SmallVectorImpl< calyx::PortInfo > &ports)
void buildAssignmentsForRegisterWrite(OpBuilder &builder, calyx::GroupOp groupOp, calyx::ComponentOp componentOp, calyx::RegisterOp &reg, Value inputValue)
Creates register assignment operations within the provided groupOp.
DenseMap< const mlir::RewritePattern *, SmallPtrSet< Operation *, 16 > > PatternApplicationState
Extra state that is passed to all PartialLoweringPatterns so they can record when they have run on an...
PredicateInfo getPredicateInfo(mlir::arith::CmpFPredicate pred)
Type convIndexType(OpBuilder &builder, Type type)
LogicalResult applyModuleOpConversion(mlir::ModuleOp, StringRef topLevelFunction)
Helper to update the top-level ModuleOp to set the entrypoing function.
WalkResult getCiderSourceLocationMetadata(calyx::ComponentOp component, SmallVectorImpl< Attribute > &sourceLocations)
bool matchConstantOp(Operation *op, APInt &value)
unsigned handleZeroWidth(int64_t dim)
hw::ConstantOp createConstant(Location loc, OpBuilder &builder, ComponentOp component, size_t width, size_t value)
A helper function to create constants in the HW dialect.
calyx::RegisterOp createRegister(Location loc, OpBuilder &builder, ComponentOp component, size_t width, Twine prefix)
Creates a RegisterOp, with input and output port bit widths defined by width.
bool noStoresToMemory(Value memoryReference)
bool singleLoadFromMemory(Value memoryReference)
std::string getInstanceName(mlir::func::CallOp callOp)
A helper function to get the instance name.
Value createOrFoldNot(Location loc, Value value, OpBuilder &builder, bool twoState=false)
Create a `‘Not’' gate on a value.
Definition: CombOps.cpp:48
static constexpr std::string_view sPortNameAttr
Definition: SCFToCalyx.h:29
static LogicalResult buildAllocOp(ComponentLoweringState &componentState, PatternRewriter &rewriter, TAllocOp allocOp)
Definition: SCFToCalyx.cpp:938
std::variant< calyx::GroupOp, WhileScheduleable, ForScheduleable, IfScheduleable, CallScheduleable, ParScheduleable > Scheduleable
A variant of types representing scheduleable operations.
Definition: SCFToCalyx.cpp:130
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21
std::unique_ptr< OperationPass< ModuleOp > > createSCFToCalyxPass()
Create an SCF to Calyx conversion pass.
def reg(value, clock, reset=None, reset_value=None, name=None, sym_name=None)
Definition: seq.py:21
This holds information about the port for either a Component or Cell.
Definition: CalyxOps.h:89
Predicate information for the floating point comparisons.
calyx::InstanceOp instanceOp
Instance for invoking.
Definition: SCFToCalyx.cpp:117
ScfForOp forOp
For operation to schedule.
Definition: SCFToCalyx.cpp:110
Creates a new Calyx component for each FuncOp in the program.
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
scf::ParallelOp parOp
Parallel operation to schedule.
Definition: SCFToCalyx.cpp:124
ScfWhileOp whileOp
While operation to schedule.
Definition: SCFToCalyx.cpp:105