CIRCT  18.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 
14 #include "../PassDetail.h"
19 #include "circt/Dialect/HW/HWOps.h"
20 #include "mlir/Conversion/LLVMCommon/ConversionTarget.h"
21 #include "mlir/Conversion/LLVMCommon/Pattern.h"
22 #include "mlir/Dialect/Arith/IR/Arith.h"
23 #include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
24 #include "mlir/Dialect/Func/IR/FuncOps.h"
25 #include "mlir/Dialect/MemRef/IR/MemRef.h"
26 #include "mlir/Dialect/SCF/IR/SCF.h"
27 #include "mlir/IR/AsmState.h"
28 #include "mlir/IR/Matchers.h"
29 #include "mlir/Support/LogicalResult.h"
30 #include "mlir/Transforms/GreedyPatternRewriteDriver.h"
31 #include "llvm/ADT/TypeSwitch.h"
32 
33 #include <variant>
34 
35 using namespace llvm;
36 using namespace mlir;
37 using namespace mlir::arith;
38 using namespace mlir::cf;
39 using namespace mlir::func;
40 
41 namespace circt {
42 class ComponentLoweringStateInterface;
43 namespace scftocalyx {
44 
45 //===----------------------------------------------------------------------===//
46 // Utility types
47 //===----------------------------------------------------------------------===//
48 
49 class ScfWhileOp : public calyx::WhileOpInterface<scf::WhileOp> {
50 public:
51  explicit ScfWhileOp(scf::WhileOp op)
52  : calyx::WhileOpInterface<scf::WhileOp>(op) {}
53 
54  Block::BlockArgListType getBodyArgs() override {
55  return getOperation().getAfterArguments();
56  }
57 
58  Block *getBodyBlock() override { return &getOperation().getAfter().front(); }
59 
60  Block *getConditionBlock() override {
61  return &getOperation().getBefore().front();
62  }
63 
64  Value getConditionValue() override {
65  return getOperation().getConditionOp().getOperand(0);
66  }
67 
68  std::optional<int64_t> getBound() override { return std::nullopt; }
69 };
70 
71 class ScfForOp : public calyx::RepeatOpInterface<scf::ForOp> {
72 public:
73  explicit ScfForOp(scf::ForOp op) : calyx::RepeatOpInterface<scf::ForOp>(op) {}
74 
75  Block::BlockArgListType getBodyArgs() override {
76  return getOperation().getRegion().getArguments();
77  }
78 
79  Block *getBodyBlock() override {
80  return &getOperation().getRegion().getBlocks().front();
81  }
82 
83  std::optional<int64_t> getBound() override {
84  return constantTripCount(getOperation().getLowerBound(),
85  getOperation().getUpperBound(),
86  getOperation().getStep());
87  }
88 };
89 
90 //===----------------------------------------------------------------------===//
91 // Lowering state classes
92 //===----------------------------------------------------------------------===//
93 
95  /// While operation to schedule.
97 };
98 
100  /// For operation to schedule.
102  /// Bound
103  uint64_t bound;
104 };
105 
107  /// Instance for invoking.
108  calyx::InstanceOp instanceOp;
109  // CallOp for getting the arguments.
110  func::CallOp callOp;
111 };
112 
113 /// A variant of types representing scheduleable operations.
114 using Scheduleable = std::variant<calyx::GroupOp, WhileScheduleable,
116 
118  : calyx::LoopLoweringStateInterface<ScfWhileOp> {
119 public:
120  SmallVector<calyx::GroupOp> getWhileLoopInitGroups(ScfWhileOp op) {
121  return getLoopInitGroups(std::move(op));
122  }
124  OpBuilder &builder, ScfWhileOp op, calyx::ComponentOp componentOp,
125  Twine uniqueSuffix, MutableArrayRef<OpOperand> ops) {
126  return buildLoopIterArgAssignments(builder, std::move(op), componentOp,
127  uniqueSuffix, ops);
128  }
129  void addWhileLoopIterReg(ScfWhileOp op, calyx::RegisterOp reg, unsigned idx) {
130  return addLoopIterReg(std::move(op), reg, idx);
131  }
132  const DenseMap<unsigned, calyx::RegisterOp> &
134  return getLoopIterRegs(std::move(op));
135  }
136  void setWhileLoopLatchGroup(ScfWhileOp op, calyx::GroupOp group) {
137  return setLoopLatchGroup(std::move(op), group);
138  }
139  calyx::GroupOp getWhileLoopLatchGroup(ScfWhileOp op) {
140  return getLoopLatchGroup(std::move(op));
141  }
143  SmallVector<calyx::GroupOp> groups) {
144  return setLoopInitGroups(std::move(op), std::move(groups));
145  }
146 };
147 
150 public:
151  SmallVector<calyx::GroupOp> getForLoopInitGroups(ScfForOp op) {
152  return getLoopInitGroups(std::move(op));
153  }
155  OpBuilder &builder, ScfForOp op, calyx::ComponentOp componentOp,
156  Twine uniqueSuffix, MutableArrayRef<OpOperand> ops) {
157  return buildLoopIterArgAssignments(builder, std::move(op), componentOp,
158  uniqueSuffix, ops);
159  }
160  void addForLoopIterReg(ScfForOp op, calyx::RegisterOp reg, unsigned idx) {
161  return addLoopIterReg(std::move(op), reg, idx);
162  }
163  const DenseMap<unsigned, calyx::RegisterOp> &getForLoopIterRegs(ScfForOp op) {
164  return getLoopIterRegs(std::move(op));
165  }
166  calyx::RegisterOp getForLoopIterReg(ScfForOp op, unsigned idx) {
167  return getLoopIterReg(std::move(op), idx);
168  }
169  void setForLoopLatchGroup(ScfForOp op, calyx::GroupOp group) {
170  return setLoopLatchGroup(std::move(op), group);
171  }
172  calyx::GroupOp getForLoopLatchGroup(ScfForOp op) {
173  return getLoopLatchGroup(std::move(op));
174  }
175  void setForLoopInitGroups(ScfForOp op, SmallVector<calyx::GroupOp> groups) {
176  return setLoopInitGroups(std::move(op), std::move(groups));
177  }
178 };
179 
180 /// Handles the current state of lowering of a Calyx component. It is mainly
181 /// used as a key/value store for recording information during partial lowering,
182 /// which is required at later lowering passes.
186  public calyx::SchedulerInterface<Scheduleable> {
187 public:
188  ComponentLoweringState(calyx::ComponentOp component)
189  : calyx::ComponentLoweringStateInterface(component) {}
190 };
191 
192 //===----------------------------------------------------------------------===//
193 // Conversion patterns
194 //===----------------------------------------------------------------------===//
195 
196 /// Iterate through the operations of a source function and instantiate
197 /// components or primitives based on the type of the operations.
199  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
200 
201  LogicalResult
203  PatternRewriter &rewriter) const override {
204  /// We walk the operations of the funcOp to ensure that all def's have
205  /// been visited before their uses.
206  bool opBuiltSuccessfully = true;
207  funcOp.walk([&](Operation *_op) {
208  opBuiltSuccessfully &=
209  TypeSwitch<mlir::Operation *, bool>(_op)
210  .template Case<arith::ConstantOp, ReturnOp, BranchOpInterface,
211  /// SCF
212  scf::YieldOp, scf::WhileOp, scf::ForOp,
213  /// memref
214  memref::AllocOp, memref::AllocaOp, memref::LoadOp,
215  memref::StoreOp,
216  /// standard arithmetic
217  AddIOp, SubIOp, CmpIOp, ShLIOp, ShRUIOp, ShRSIOp,
218  AndIOp, XOrIOp, OrIOp, ExtUIOp, ExtSIOp, TruncIOp,
219  MulIOp, DivUIOp, DivSIOp, RemUIOp, RemSIOp,
220  SelectOp, IndexCastOp, CallOp>(
221  [&](auto op) { return buildOp(rewriter, op).succeeded(); })
222  .template Case<FuncOp, scf::ConditionOp>([&](auto) {
223  /// Skip: these special cases will be handled separately.
224  return true;
225  })
226  .Default([&](auto op) {
227  op->emitError() << "Unhandled operation during BuildOpGroups()";
228  return false;
229  });
230 
231  return opBuiltSuccessfully ? WalkResult::advance()
232  : WalkResult::interrupt();
233  });
234 
235  return success(opBuiltSuccessfully);
236  }
237 
238 private:
239  /// Op builder specializations.
240  LogicalResult buildOp(PatternRewriter &rewriter, scf::YieldOp yieldOp) const;
241  LogicalResult buildOp(PatternRewriter &rewriter,
242  BranchOpInterface brOp) const;
243  LogicalResult buildOp(PatternRewriter &rewriter,
244  arith::ConstantOp constOp) const;
245  LogicalResult buildOp(PatternRewriter &rewriter, SelectOp op) const;
246  LogicalResult buildOp(PatternRewriter &rewriter, AddIOp op) const;
247  LogicalResult buildOp(PatternRewriter &rewriter, SubIOp op) const;
248  LogicalResult buildOp(PatternRewriter &rewriter, MulIOp op) const;
249  LogicalResult buildOp(PatternRewriter &rewriter, DivUIOp op) const;
250  LogicalResult buildOp(PatternRewriter &rewriter, DivSIOp op) const;
251  LogicalResult buildOp(PatternRewriter &rewriter, RemUIOp op) const;
252  LogicalResult buildOp(PatternRewriter &rewriter, RemSIOp op) const;
253  LogicalResult buildOp(PatternRewriter &rewriter, ShRUIOp op) const;
254  LogicalResult buildOp(PatternRewriter &rewriter, ShRSIOp op) const;
255  LogicalResult buildOp(PatternRewriter &rewriter, ShLIOp op) const;
256  LogicalResult buildOp(PatternRewriter &rewriter, AndIOp op) const;
257  LogicalResult buildOp(PatternRewriter &rewriter, OrIOp op) const;
258  LogicalResult buildOp(PatternRewriter &rewriter, XOrIOp op) const;
259  LogicalResult buildOp(PatternRewriter &rewriter, CmpIOp op) const;
260  LogicalResult buildOp(PatternRewriter &rewriter, TruncIOp op) const;
261  LogicalResult buildOp(PatternRewriter &rewriter, ExtUIOp op) const;
262  LogicalResult buildOp(PatternRewriter &rewriter, ExtSIOp op) const;
263  LogicalResult buildOp(PatternRewriter &rewriter, ReturnOp op) const;
264  LogicalResult buildOp(PatternRewriter &rewriter, IndexCastOp op) const;
265  LogicalResult buildOp(PatternRewriter &rewriter, memref::AllocOp op) const;
266  LogicalResult buildOp(PatternRewriter &rewriter, memref::AllocaOp op) const;
267  LogicalResult buildOp(PatternRewriter &rewriter, memref::LoadOp op) const;
268  LogicalResult buildOp(PatternRewriter &rewriter, memref::StoreOp op) const;
269  LogicalResult buildOp(PatternRewriter &rewriter, scf::WhileOp whileOp) const;
270  LogicalResult buildOp(PatternRewriter &rewriter, scf::ForOp forOp) const;
271  LogicalResult buildOp(PatternRewriter &rewriter, CallOp callOp) const;
272 
273  /// buildLibraryOp will build a TCalyxLibOp inside a TGroupOp based on the
274  /// source operation TSrcOp.
275  template <typename TGroupOp, typename TCalyxLibOp, typename TSrcOp>
276  LogicalResult buildLibraryOp(PatternRewriter &rewriter, TSrcOp op,
277  TypeRange srcTypes, TypeRange dstTypes) const {
278  SmallVector<Type> types;
279  llvm::append_range(types, srcTypes);
280  llvm::append_range(types, dstTypes);
281 
282  auto calyxOp =
283  getState<ComponentLoweringState>().getNewLibraryOpInstance<TCalyxLibOp>(
284  rewriter, op.getLoc(), types);
285 
286  auto directions = calyxOp.portDirections();
287  SmallVector<Value, 4> opInputPorts;
288  SmallVector<Value, 4> opOutputPorts;
289  for (auto dir : enumerate(directions)) {
290  if (dir.value() == calyx::Direction::Input)
291  opInputPorts.push_back(calyxOp.getResult(dir.index()));
292  else
293  opOutputPorts.push_back(calyxOp.getResult(dir.index()));
294  }
295  assert(
296  opInputPorts.size() == op->getNumOperands() &&
297  opOutputPorts.size() == op->getNumResults() &&
298  "Expected an equal number of in/out ports in the Calyx library op with "
299  "respect to the number of operands/results of the source operation.");
300 
301  /// Create assignments to the inputs of the library op.
302  auto group = createGroupForOp<TGroupOp>(rewriter, op);
303  rewriter.setInsertionPointToEnd(group.getBodyBlock());
304  for (auto dstOp : enumerate(opInputPorts))
305  rewriter.create<calyx::AssignOp>(op.getLoc(), dstOp.value(),
306  op->getOperand(dstOp.index()));
307 
308  /// Replace the result values of the source operator with the new operator.
309  for (auto res : enumerate(opOutputPorts)) {
310  getState<ComponentLoweringState>().registerEvaluatingGroup(res.value(),
311  group);
312  op->getResult(res.index()).replaceAllUsesWith(res.value());
313  }
314  return success();
315  }
316 
317  /// buildLibraryOp which provides in- and output types based on the operands
318  /// and results of the op argument.
319  template <typename TGroupOp, typename TCalyxLibOp, typename TSrcOp>
320  LogicalResult buildLibraryOp(PatternRewriter &rewriter, TSrcOp op) const {
321  return buildLibraryOp<TGroupOp, TCalyxLibOp, TSrcOp>(
322  rewriter, op, op.getOperandTypes(), op->getResultTypes());
323  }
324 
325  /// Creates a group named by the basic block which the input op resides in.
326  template <typename TGroupOp>
327  TGroupOp createGroupForOp(PatternRewriter &rewriter, Operation *op) const {
328  Block *block = op->getBlock();
329  auto groupName = getState<ComponentLoweringState>().getUniqueName(
330  loweringState().blockName(block));
331  return calyx::createGroup<TGroupOp>(
332  rewriter, getState<ComponentLoweringState>().getComponentOp(),
333  op->getLoc(), groupName);
334  }
335 
336  /// buildLibraryBinaryPipeOp will build a TCalyxLibBinaryPipeOp, to
337  /// deal with MulIOp, DivUIOp and RemUIOp.
338  template <typename TOpType, typename TSrcOp>
339  LogicalResult buildLibraryBinaryPipeOp(PatternRewriter &rewriter, TSrcOp op,
340  TOpType opPipe, Value out) const {
341  StringRef opName = TSrcOp::getOperationName().split(".").second;
342  Location loc = op.getLoc();
343  Type width = op.getResult().getType();
344  // Pass the result from the Operation to the Calyx primitive.
345  op.getResult().replaceAllUsesWith(out);
346  auto reg = createRegister(
347  op.getLoc(), rewriter, getComponent(), width.getIntOrFloatBitWidth(),
348  getState<ComponentLoweringState>().getUniqueName(opName));
349  // Operation pipelines are not combinational, so a GroupOp is required.
350  auto group = createGroupForOp<calyx::GroupOp>(rewriter, op);
351  OpBuilder builder(group->getRegion(0));
352  getState<ComponentLoweringState>().addBlockScheduleable(op->getBlock(),
353  group);
354 
355  rewriter.setInsertionPointToEnd(group.getBodyBlock());
356  rewriter.create<calyx::AssignOp>(loc, opPipe.getLeft(), op.getLhs());
357  rewriter.create<calyx::AssignOp>(loc, opPipe.getRight(), op.getRhs());
358  // Write the output to this register.
359  rewriter.create<calyx::AssignOp>(loc, reg.getIn(), out);
360  // The write enable port is high when the pipeline is done.
361  rewriter.create<calyx::AssignOp>(loc, reg.getWriteEn(), opPipe.getDone());
362  // Set pipelineOp to high as long as its done signal is not high.
363  // This prevents the pipelineOP from executing for the cycle that we write
364  // to register. To get !(pipelineOp.done) we do 1 xor pipelineOp.done
365  hw::ConstantOp c1 = createConstant(loc, rewriter, getComponent(), 1, 1);
366  rewriter.create<calyx::AssignOp>(
367  loc, opPipe.getGo(), c1,
368  comb::createOrFoldNot(group.getLoc(), opPipe.getDone(), builder));
369  // The group is done when the register write is complete.
370  rewriter.create<calyx::GroupDoneOp>(loc, reg.getDone());
371 
372  // Register the values for the pipeline.
373  getState<ComponentLoweringState>().registerEvaluatingGroup(out, group);
374  getState<ComponentLoweringState>().registerEvaluatingGroup(opPipe.getLeft(),
375  group);
376  getState<ComponentLoweringState>().registerEvaluatingGroup(
377  opPipe.getRight(), group);
378 
379  return success();
380  }
381 
382  /// Creates assignments within the provided group to the address ports of the
383  /// memoryOp based on the provided addressValues.
384  void assignAddressPorts(PatternRewriter &rewriter, Location loc,
385  calyx::GroupInterface group,
386  calyx::MemoryInterface memoryInterface,
387  Operation::operand_range addressValues) const {
388  IRRewriter::InsertionGuard guard(rewriter);
389  rewriter.setInsertionPointToEnd(group.getBody());
390  auto addrPorts = memoryInterface.addrPorts();
391  if (addressValues.empty()) {
392  assert(
393  addrPorts.size() == 1 &&
394  "We expected a 1 dimensional memory of size 1 because there were no "
395  "address assignment values");
396  // Assign to address 1'd0 in memory.
397  rewriter.create<calyx::AssignOp>(
398  loc, addrPorts[0],
399  createConstant(loc, rewriter, getComponent(), 1, 0));
400  } else {
401  assert(addrPorts.size() == addressValues.size() &&
402  "Mismatch between number of address ports of the provided memory "
403  "and address assignment values");
404  for (auto address : enumerate(addressValues))
405  rewriter.create<calyx::AssignOp>(loc, addrPorts[address.index()],
406  address.value());
407  }
408  }
409 };
410 
411 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
412  memref::LoadOp loadOp) const {
413  Value memref = loadOp.getMemref();
414  auto memoryInterface =
415  getState<ComponentLoweringState>().getMemoryInterface(memref);
416  auto group = createGroupForOp<calyx::GroupOp>(rewriter, loadOp);
417  assignAddressPorts(rewriter, loadOp.getLoc(), group, memoryInterface,
418  loadOp.getIndices());
419 
420  rewriter.setInsertionPointToEnd(group.getBodyBlock());
421 
422  bool needReg = true;
423  Value res;
424  Value regWriteEn =
425  createConstant(loadOp.getLoc(), rewriter, getComponent(), 1, 1);
426  if (memoryInterface.readEnOpt().has_value()) {
427  auto oneI1 =
428  calyx::createConstant(loadOp.getLoc(), rewriter, getComponent(), 1, 1);
429  rewriter.create<calyx::AssignOp>(loadOp.getLoc(), memoryInterface.readEn(),
430  oneI1);
431  regWriteEn = memoryInterface.readDone();
432  if (calyx::noStoresToMemory(memref) &&
433  calyx::singleLoadFromMemory(memref)) {
434  // Single load from memory; we do not need to write the output to a
435  // register. The readData value will be held until readEn is asserted
436  // again
437  needReg = false;
438  rewriter.create<calyx::GroupDoneOp>(loadOp.getLoc(),
439  memoryInterface.readDone());
440  // We refrain from replacing the loadOp result with
441  // memoryInterface.readData, since multiple loadOp's need to be converted
442  // to a single memory's ReadData. If this replacement is done now, we lose
443  // the link between which SSA memref::LoadOp values map to which groups
444  // for loading a value from the Calyx memory. At this point of lowering,
445  // we keep the memref::LoadOp SSA value, and do value replacement _after_
446  // control has been generated (see LateSSAReplacement). This is *vital*
447  // for things such as calyx::InlineCombGroups to be able to properly track
448  // which memory assignment groups belong to which accesses.
449  res = loadOp.getResult();
450  }
451  }
452 
453  if (needReg) {
454  // Multiple loads from the same memory; In this case, we _may_ have a
455  // structural hazard in the design we generate. To get around this, we
456  // conservatively place a register in front of each load operation, and
457  // replace all uses of the loaded value with the register output. Reading
458  // for sequential memories will cause a read to take at least 2 cycles,
459  // but it will usually be better because combinational reads on memories
460  // can significantly decrease the maximum achievable frequency.
461  auto reg = createRegister(
462  loadOp.getLoc(), rewriter, getComponent(),
463  loadOp.getMemRefType().getElementTypeBitWidth(),
464  getState<ComponentLoweringState>().getUniqueName("load"));
465  rewriter.setInsertionPointToEnd(group.getBodyBlock());
466  rewriter.create<calyx::AssignOp>(loadOp.getLoc(), reg.getIn(),
467  memoryInterface.readData());
468  rewriter.create<calyx::AssignOp>(loadOp.getLoc(), reg.getWriteEn(),
469  regWriteEn);
470  rewriter.create<calyx::GroupDoneOp>(loadOp.getLoc(), reg.getDone());
471  loadOp.getResult().replaceAllUsesWith(reg.getOut());
472  res = reg.getOut();
473  }
474 
475  getState<ComponentLoweringState>().registerEvaluatingGroup(res, group);
476  getState<ComponentLoweringState>().addBlockScheduleable(loadOp->getBlock(),
477  group);
478  return success();
479 }
480 
481 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
482  memref::StoreOp storeOp) const {
483  auto memoryInterface = getState<ComponentLoweringState>().getMemoryInterface(
484  storeOp.getMemref());
485  auto group = createGroupForOp<calyx::GroupOp>(rewriter, storeOp);
486 
487  // This is a sequential group, so register it as being scheduleable for the
488  // block.
489  getState<ComponentLoweringState>().addBlockScheduleable(storeOp->getBlock(),
490  group);
491  assignAddressPorts(rewriter, storeOp.getLoc(), group, memoryInterface,
492  storeOp.getIndices());
493  rewriter.setInsertionPointToEnd(group.getBodyBlock());
494  rewriter.create<calyx::AssignOp>(
495  storeOp.getLoc(), memoryInterface.writeData(), storeOp.getValueToStore());
496  rewriter.create<calyx::AssignOp>(
497  storeOp.getLoc(), memoryInterface.writeEn(),
498  createConstant(storeOp.getLoc(), rewriter, getComponent(), 1, 1));
499  rewriter.create<calyx::GroupDoneOp>(storeOp.getLoc(),
500  memoryInterface.writeDone());
501 
502  return success();
503 }
504 
505 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
506  MulIOp mul) const {
507  Location loc = mul.getLoc();
508  Type width = mul.getResult().getType(), one = rewriter.getI1Type();
509  auto mulPipe =
510  getState<ComponentLoweringState>()
511  .getNewLibraryOpInstance<calyx::MultPipeLibOp>(
512  rewriter, loc, {one, one, one, width, width, width, one});
513  return buildLibraryBinaryPipeOp<calyx::MultPipeLibOp>(
514  rewriter, mul, mulPipe,
515  /*out=*/mulPipe.getOut());
516 }
517 
518 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
519  DivUIOp div) const {
520  Location loc = div.getLoc();
521  Type width = div.getResult().getType(), one = rewriter.getI1Type();
522  auto divPipe =
523  getState<ComponentLoweringState>()
524  .getNewLibraryOpInstance<calyx::DivUPipeLibOp>(
525  rewriter, loc, {one, one, one, width, width, width, one});
526  return buildLibraryBinaryPipeOp<calyx::DivUPipeLibOp>(
527  rewriter, div, divPipe,
528  /*out=*/divPipe.getOut());
529 }
530 
531 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
532  DivSIOp div) const {
533  Location loc = div.getLoc();
534  Type width = div.getResult().getType(), one = rewriter.getI1Type();
535  auto divPipe =
536  getState<ComponentLoweringState>()
537  .getNewLibraryOpInstance<calyx::DivSPipeLibOp>(
538  rewriter, loc, {one, one, one, width, width, width, one});
539  return buildLibraryBinaryPipeOp<calyx::DivSPipeLibOp>(
540  rewriter, div, divPipe,
541  /*out=*/divPipe.getOut());
542 }
543 
544 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
545  RemUIOp rem) const {
546  Location loc = rem.getLoc();
547  Type width = rem.getResult().getType(), one = rewriter.getI1Type();
548  auto remPipe =
549  getState<ComponentLoweringState>()
550  .getNewLibraryOpInstance<calyx::RemUPipeLibOp>(
551  rewriter, loc, {one, one, one, width, width, width, one});
552  return buildLibraryBinaryPipeOp<calyx::RemUPipeLibOp>(
553  rewriter, rem, remPipe,
554  /*out=*/remPipe.getOut());
555 }
556 
557 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
558  RemSIOp rem) const {
559  Location loc = rem.getLoc();
560  Type width = rem.getResult().getType(), one = rewriter.getI1Type();
561  auto remPipe =
562  getState<ComponentLoweringState>()
563  .getNewLibraryOpInstance<calyx::RemSPipeLibOp>(
564  rewriter, loc, {one, one, one, width, width, width, one});
565  return buildLibraryBinaryPipeOp<calyx::RemSPipeLibOp>(
566  rewriter, rem, remPipe,
567  /*out=*/remPipe.getOut());
568 }
569 
570 template <typename TAllocOp>
571 static LogicalResult buildAllocOp(ComponentLoweringState &componentState,
572  PatternRewriter &rewriter, TAllocOp allocOp) {
573  rewriter.setInsertionPointToStart(
574  componentState.getComponentOp().getBodyBlock());
575  MemRefType memtype = allocOp.getType();
576  SmallVector<int64_t> addrSizes;
577  SmallVector<int64_t> sizes;
578  for (int64_t dim : memtype.getShape()) {
579  sizes.push_back(dim);
580  addrSizes.push_back(calyx::handleZeroWidth(dim));
581  }
582  // If memref has no size (e.g., memref<i32>) create a 1 dimensional memory of
583  // size 1.
584  if (sizes.empty() && addrSizes.empty()) {
585  sizes.push_back(1);
586  addrSizes.push_back(1);
587  }
588  auto memoryOp = rewriter.create<calyx::SeqMemoryOp>(
589  allocOp.getLoc(), componentState.getUniqueName("mem"),
590  memtype.getElementType().getIntOrFloatBitWidth(), sizes, addrSizes);
591  // Externalize memories by default. This makes it easier for the native
592  // compiler to provide initialized memories.
593  memoryOp->setAttr("external",
594  IntegerAttr::get(rewriter.getI1Type(), llvm::APInt(1, 1)));
595  componentState.registerMemoryInterface(allocOp.getResult(),
596  calyx::MemoryInterface(memoryOp));
597  return success();
598 }
599 
600 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
601  memref::AllocOp allocOp) const {
602  return buildAllocOp(getState<ComponentLoweringState>(), rewriter, allocOp);
603 }
604 
605 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
606  memref::AllocaOp allocOp) const {
607  return buildAllocOp(getState<ComponentLoweringState>(), rewriter, allocOp);
608 }
609 
610 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
611  scf::YieldOp yieldOp) const {
612  if (yieldOp.getOperands().empty()) {
613  // If yield operands are empty, we assume we have a for loop.
614  auto forOp = dyn_cast<scf::ForOp>(yieldOp->getParentOp());
615  assert(forOp && "Empty yieldOps should only be located within ForOps");
616  ScfForOp forOpInterface(forOp);
617 
618  // Get the ForLoop's Induction Register.
619  auto inductionReg =
620  getState<ComponentLoweringState>().getForLoopIterReg(forOpInterface, 0);
621 
622  Type regWidth = inductionReg.getOut().getType();
623  // Adder should have same width as the inductionReg.
624  SmallVector<Type> types(3, regWidth);
625  auto addOp = getState<ComponentLoweringState>()
626  .getNewLibraryOpInstance<calyx::AddLibOp>(
627  rewriter, forOp.getLoc(), types);
628 
629  auto directions = addOp.portDirections();
630  // For an add operation, we expect two input ports and one output port
631  SmallVector<Value, 2> opInputPorts;
632  Value opOutputPort;
633  for (auto dir : enumerate(directions)) {
634  switch (dir.value()) {
636  opInputPorts.push_back(addOp.getResult(dir.index()));
637  break;
638  }
640  opOutputPort = addOp.getResult(dir.index());
641  break;
642  }
643  }
644  }
645 
646  // "Latch Group" increments inductionReg by forLoop's step value.
647  calyx::ComponentOp componentOp =
648  getState<ComponentLoweringState>().getComponentOp();
649  SmallVector<StringRef, 4> groupIdentifier = {
650  "incr", getState<ComponentLoweringState>().getUniqueName(forOp),
651  "induction", "var"};
652  auto groupOp = calyx::createGroup<calyx::GroupOp>(
653  rewriter, componentOp, forOp.getLoc(),
654  llvm::join(groupIdentifier, "_"));
655  rewriter.setInsertionPointToEnd(groupOp.getBodyBlock());
656 
657  // Assign inductionReg.out to the left port of the adder.
658  Value leftOp = opInputPorts.front();
659  rewriter.create<calyx::AssignOp>(forOp.getLoc(), leftOp,
660  inductionReg.getOut());
661  // Assign forOp.getConstantStep to the right port of the adder.
662  Value rightOp = opInputPorts.back();
663  rewriter.create<calyx::AssignOp>(
664  forOp.getLoc(), rightOp,
665  createConstant(forOp->getLoc(), rewriter, componentOp,
666  regWidth.getIntOrFloatBitWidth(),
667  forOp.getConstantStep().value().getSExtValue()));
668  // Assign adder's output port to inductionReg.
669  buildAssignmentsForRegisterWrite(rewriter, groupOp, componentOp,
670  inductionReg, opOutputPort);
671  // Set group as For Loop's "latch" group.
672  getState<ComponentLoweringState>().setForLoopLatchGroup(forOpInterface,
673  groupOp);
674  getState<ComponentLoweringState>().registerEvaluatingGroup(opOutputPort,
675  groupOp);
676  return success();
677  }
678  // If yieldOp for a for loop is not empty, then we do not transform for loop.
679  if (dyn_cast<scf::ForOp>(yieldOp->getParentOp())) {
680  return yieldOp.getOperation()->emitError()
681  << "Currently do not support non-empty yield operations inside for "
682  "loops. Run --scf-for-to-while before running --scf-to-calyx.";
683  }
684 
685  auto whileOp = dyn_cast<scf::WhileOp>(yieldOp->getParentOp());
686  if (!whileOp) {
687  return yieldOp.getOperation()->emitError()
688  << "Currently only support yield operations inside for and while "
689  "loops.";
690  }
691  ScfWhileOp whileOpInterface(whileOp);
692 
693  auto assignGroup =
694  getState<ComponentLoweringState>().buildWhileLoopIterArgAssignments(
695  rewriter, whileOpInterface,
696  getState<ComponentLoweringState>().getComponentOp(),
697  getState<ComponentLoweringState>().getUniqueName(whileOp) + "_latch",
698  yieldOp->getOpOperands());
699  getState<ComponentLoweringState>().setWhileLoopLatchGroup(whileOpInterface,
700  assignGroup);
701  return success();
702 }
703 
704 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
705  BranchOpInterface brOp) const {
706  /// Branch argument passing group creation
707  /// Branch operands are passed through registers. In BuildBasicBlockRegs we
708  /// created registers for all branch arguments of each block. We now
709  /// create groups for assigning values to these registers.
710  Block *srcBlock = brOp->getBlock();
711  for (auto succBlock : enumerate(brOp->getSuccessors())) {
712  auto succOperands = brOp.getSuccessorOperands(succBlock.index());
713  if (succOperands.empty())
714  continue;
715  // Create operand passing group
716  std::string groupName = loweringState().blockName(srcBlock) + "_to_" +
717  loweringState().blockName(succBlock.value());
718  auto groupOp = calyx::createGroup<calyx::GroupOp>(rewriter, getComponent(),
719  brOp.getLoc(), groupName);
720  // Fetch block argument registers associated with the basic block
721  auto dstBlockArgRegs =
722  getState<ComponentLoweringState>().getBlockArgRegs(succBlock.value());
723  // Create register assignment for each block argument
724  for (auto arg : enumerate(succOperands.getForwardedOperands())) {
725  auto reg = dstBlockArgRegs[arg.index()];
727  rewriter, groupOp,
728  getState<ComponentLoweringState>().getComponentOp(), reg,
729  arg.value());
730  }
731  /// Register the group as a block argument group, to be executed
732  /// when entering the successor block from this block (srcBlock).
733  getState<ComponentLoweringState>().addBlockArgGroup(
734  srcBlock, succBlock.value(), groupOp);
735  }
736  return success();
737 }
738 
739 /// For each return statement, we create a new group for assigning to the
740 /// previously created return value registers.
741 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
742  ReturnOp retOp) const {
743  if (retOp.getNumOperands() == 0)
744  return success();
745 
746  std::string groupName =
747  getState<ComponentLoweringState>().getUniqueName("ret_assign");
748  auto groupOp = calyx::createGroup<calyx::GroupOp>(rewriter, getComponent(),
749  retOp.getLoc(), groupName);
750  for (auto op : enumerate(retOp.getOperands())) {
751  auto reg = getState<ComponentLoweringState>().getReturnReg(op.index());
753  rewriter, groupOp, getState<ComponentLoweringState>().getComponentOp(),
754  reg, op.value());
755  }
756  /// Schedule group for execution for when executing the return op block.
757  getState<ComponentLoweringState>().addBlockScheduleable(retOp->getBlock(),
758  groupOp);
759  return success();
760 }
761 
762 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
763  arith::ConstantOp constOp) const {
764  /// Move constant operations to the compOp body as hw::ConstantOp's.
765  APInt value;
766  calyx::matchConstantOp(constOp, value);
767  auto hwConstOp = rewriter.replaceOpWithNewOp<hw::ConstantOp>(constOp, value);
768  hwConstOp->moveAfter(getComponent().getBodyBlock(),
769  getComponent().getBodyBlock()->begin());
770  return success();
771 }
772 
773 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
774  AddIOp op) const {
775  return buildLibraryOp<calyx::CombGroupOp, calyx::AddLibOp>(rewriter, op);
776 }
777 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
778  SubIOp op) const {
779  return buildLibraryOp<calyx::CombGroupOp, calyx::SubLibOp>(rewriter, op);
780 }
781 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
782  ShRUIOp op) const {
783  return buildLibraryOp<calyx::CombGroupOp, calyx::RshLibOp>(rewriter, op);
784 }
785 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
786  ShRSIOp op) const {
787  return buildLibraryOp<calyx::CombGroupOp, calyx::SrshLibOp>(rewriter, op);
788 }
789 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
790  ShLIOp op) const {
791  return buildLibraryOp<calyx::CombGroupOp, calyx::LshLibOp>(rewriter, op);
792 }
793 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
794  AndIOp op) const {
795  return buildLibraryOp<calyx::CombGroupOp, calyx::AndLibOp>(rewriter, op);
796 }
797 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
798  OrIOp op) const {
799  return buildLibraryOp<calyx::CombGroupOp, calyx::OrLibOp>(rewriter, op);
800 }
801 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
802  XOrIOp op) const {
803  return buildLibraryOp<calyx::CombGroupOp, calyx::XorLibOp>(rewriter, op);
804 }
805 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
806  SelectOp op) const {
807  return buildLibraryOp<calyx::CombGroupOp, calyx::MuxLibOp>(rewriter, op);
808 }
809 
810 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
811  CmpIOp op) const {
812  switch (op.getPredicate()) {
813  case CmpIPredicate::eq:
814  return buildLibraryOp<calyx::CombGroupOp, calyx::EqLibOp>(rewriter, op);
815  case CmpIPredicate::ne:
816  return buildLibraryOp<calyx::CombGroupOp, calyx::NeqLibOp>(rewriter, op);
817  case CmpIPredicate::uge:
818  return buildLibraryOp<calyx::CombGroupOp, calyx::GeLibOp>(rewriter, op);
819  case CmpIPredicate::ult:
820  return buildLibraryOp<calyx::CombGroupOp, calyx::LtLibOp>(rewriter, op);
821  case CmpIPredicate::ugt:
822  return buildLibraryOp<calyx::CombGroupOp, calyx::GtLibOp>(rewriter, op);
823  case CmpIPredicate::ule:
824  return buildLibraryOp<calyx::CombGroupOp, calyx::LeLibOp>(rewriter, op);
825  case CmpIPredicate::sge:
826  return buildLibraryOp<calyx::CombGroupOp, calyx::SgeLibOp>(rewriter, op);
827  case CmpIPredicate::slt:
828  return buildLibraryOp<calyx::CombGroupOp, calyx::SltLibOp>(rewriter, op);
829  case CmpIPredicate::sgt:
830  return buildLibraryOp<calyx::CombGroupOp, calyx::SgtLibOp>(rewriter, op);
831  case CmpIPredicate::sle:
832  return buildLibraryOp<calyx::CombGroupOp, calyx::SleLibOp>(rewriter, op);
833  }
834  llvm_unreachable("unsupported comparison predicate");
835 }
836 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
837  TruncIOp op) const {
838  return buildLibraryOp<calyx::CombGroupOp, calyx::SliceLibOp>(
839  rewriter, op, {op.getOperand().getType()}, {op.getType()});
840 }
841 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
842  ExtUIOp op) const {
843  return buildLibraryOp<calyx::CombGroupOp, calyx::PadLibOp>(
844  rewriter, op, {op.getOperand().getType()}, {op.getType()});
845 }
846 
847 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
848  ExtSIOp op) const {
849  return buildLibraryOp<calyx::CombGroupOp, calyx::ExtSILibOp>(
850  rewriter, op, {op.getOperand().getType()}, {op.getType()});
851 }
852 
853 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
854  IndexCastOp op) const {
855  Type sourceType = calyx::convIndexType(rewriter, op.getOperand().getType());
856  Type targetType = calyx::convIndexType(rewriter, op.getResult().getType());
857  unsigned targetBits = targetType.getIntOrFloatBitWidth();
858  unsigned sourceBits = sourceType.getIntOrFloatBitWidth();
859  LogicalResult res = success();
860 
861  if (targetBits == sourceBits) {
862  /// Drop the index cast and replace uses of the target value with the source
863  /// value.
864  op.getResult().replaceAllUsesWith(op.getOperand());
865  } else {
866  /// pad/slice the source operand.
867  if (sourceBits > targetBits)
868  res = buildLibraryOp<calyx::CombGroupOp, calyx::SliceLibOp>(
869  rewriter, op, {sourceType}, {targetType});
870  else
871  res = buildLibraryOp<calyx::CombGroupOp, calyx::PadLibOp>(
872  rewriter, op, {sourceType}, {targetType});
873  }
874  rewriter.eraseOp(op);
875  return res;
876 }
877 
878 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
879  scf::WhileOp whileOp) const {
880  // Only need to add the whileOp to the BlockSchedulables scheduler interface.
881  // Everything else was handled in the `BuildWhileGroups` pattern.
882  ScfWhileOp scfWhileOp(whileOp);
883  getState<ComponentLoweringState>().addBlockScheduleable(
884  whileOp.getOperation()->getBlock(), WhileScheduleable{scfWhileOp});
885  return success();
886 }
887 
888 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
889  scf::ForOp forOp) const {
890  // Only need to add the forOp to the BlockSchedulables scheduler interface.
891  // Everything else was handled in the `BuildForGroups` pattern.
892  ScfForOp scfForOp(forOp);
893  // If we cannot compute the trip count of the for loop, then we should
894  // emit an error saying to use --scf-for-to-while
895  std::optional<uint64_t> bound = scfForOp.getBound();
896  if (!bound.has_value()) {
897  return scfForOp.getOperation()->emitError()
898  << "Loop bound not statically known. Should "
899  "transform into while loop using `--scf-for-to-while` before "
900  "running --lower-scf-to-calyx.";
901  }
902  getState<ComponentLoweringState>().addBlockScheduleable(
903  forOp.getOperation()->getBlock(), ForScheduleable{
904  scfForOp,
905  bound.value(),
906  });
907  return success();
908 }
909 
910 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
911  CallOp callOp) const {
912  std::string instanceName = calyx::getInstanceName(callOp);
913  calyx::InstanceOp instanceOp =
914  getState<ComponentLoweringState>().getInstance(instanceName);
915  SmallVector<Value, 4> outputPorts;
916  auto portInfos = instanceOp.getReferencedComponent().getPortInfo();
917  for (auto [idx, portInfo] : enumerate(portInfos)) {
918  if (portInfo.direction == calyx::Direction::Output)
919  outputPorts.push_back(instanceOp.getResult(idx));
920  }
921 
922  // Replacing a CallOp results in the out port of the instance.
923  for (auto [idx, result] : llvm::enumerate(callOp.getResults()))
924  rewriter.replaceAllUsesWith(result, outputPorts[idx]);
925 
926  // CallScheduleanle requires an instance, while CallOp can be used to get the
927  // input ports.
928  getState<ComponentLoweringState>().addBlockScheduleable(
929  callOp.getOperation()->getBlock(), CallScheduleable{instanceOp, callOp});
930  return success();
931 }
932 
933 /// Inlines Calyx ExecuteRegionOp operations within their parent blocks.
934 /// An execution region op (ERO) is inlined by:
935 /// i : add a sink basic block for all yield operations inside the
936 /// ERO to jump to
937 /// ii : Rewrite scf.yield calls inside the ERO to branch to the sink block
938 /// iii: inline the ERO region
939 /// TODO(#1850) evaluate the usefulness of this lowering pattern.
941  : public OpRewritePattern<scf::ExecuteRegionOp> {
942  using OpRewritePattern::OpRewritePattern;
943 
944  LogicalResult matchAndRewrite(scf::ExecuteRegionOp execOp,
945  PatternRewriter &rewriter) const override {
946  /// Determine type of "yield" operations inside the ERO.
947  TypeRange yieldTypes = execOp.getResultTypes();
948 
949  /// Create sink basic block and rewrite uses of yield results to sink block
950  /// arguments.
951  rewriter.setInsertionPointAfter(execOp);
952  auto *sinkBlock = rewriter.splitBlock(
953  execOp->getBlock(),
954  execOp.getOperation()->getIterator()->getNextNode()->getIterator());
955  sinkBlock->addArguments(
956  yieldTypes,
957  SmallVector<Location, 4>(yieldTypes.size(), rewriter.getUnknownLoc()));
958  for (auto res : enumerate(execOp.getResults()))
959  res.value().replaceAllUsesWith(sinkBlock->getArgument(res.index()));
960 
961  /// Rewrite yield calls as branches.
962  for (auto yieldOp :
963  make_early_inc_range(execOp.getRegion().getOps<scf::YieldOp>())) {
964  rewriter.setInsertionPointAfter(yieldOp);
965  rewriter.replaceOpWithNewOp<BranchOp>(yieldOp, sinkBlock,
966  yieldOp.getOperands());
967  }
968 
969  /// Inline the regionOp.
970  auto *preBlock = execOp->getBlock();
971  auto *execOpEntryBlock = &execOp.getRegion().front();
972  auto *postBlock = execOp->getBlock()->splitBlock(execOp);
973  rewriter.inlineRegionBefore(execOp.getRegion(), postBlock);
974  rewriter.mergeBlocks(postBlock, preBlock);
975  rewriter.eraseOp(execOp);
976 
977  /// Finally, erase the unused entry block of the execOp region.
978  rewriter.mergeBlocks(execOpEntryBlock, preBlock);
979 
980  return success();
981  }
982 };
983 
984 /// Creates a new Calyx component for each FuncOp in the program.
986  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
987 
988  LogicalResult
990  PatternRewriter &rewriter) const override {
991  /// Maintain a mapping between funcOp input arguments and the port index
992  /// which the argument will eventually map to.
993  DenseMap<Value, unsigned> funcOpArgRewrites;
994 
995  /// Maintain a mapping between funcOp output indexes and the component
996  /// output port index which the return value will eventually map to.
997  DenseMap<unsigned, unsigned> funcOpResultMapping;
998 
999  /// Maintain a mapping between an external memory argument (identified by a
1000  /// memref) and eventual component input- and output port indices that will
1001  /// map to the memory ports. The pair denotes the start index of the memory
1002  /// ports in the in- and output ports of the component. Ports are expected
1003  /// to be ordered in the same manner as they are added by
1004  /// calyx::appendPortsForExternalMemref.
1005  DenseMap<Value, std::pair<unsigned, unsigned>> extMemoryCompPortIndices;
1006 
1007  /// Create I/O ports. Maintain separate in/out port vectors to determine
1008  /// which port index each function argument will eventually map to.
1009  SmallVector<calyx::PortInfo> inPorts, outPorts;
1010  FunctionType funcType = funcOp.getFunctionType();
1011  unsigned extMemCounter = 0;
1012  for (auto arg : enumerate(funcOp.getArguments())) {
1013  if (arg.value().getType().isa<MemRefType>()) {
1014  /// External memories
1015  auto memName =
1016  "ext_mem" + std::to_string(extMemoryCompPortIndices.size());
1017  extMemoryCompPortIndices[arg.value()] = {inPorts.size(),
1018  outPorts.size()};
1019  calyx::appendPortsForExternalMemref(rewriter, memName, arg.value(),
1020  extMemCounter++, inPorts, outPorts);
1021  } else {
1022  /// Single-port arguments
1023  std::string inName;
1024  if (auto portNameAttr = funcOp.getArgAttrOfType<StringAttr>(
1025  arg.index(), scfToCalyx::sPortNameAttr))
1026  inName = portNameAttr.str();
1027  else
1028  inName = "in" + std::to_string(arg.index());
1029  funcOpArgRewrites[arg.value()] = inPorts.size();
1030  inPorts.push_back(calyx::PortInfo{
1031  rewriter.getStringAttr(inName),
1032  calyx::convIndexType(rewriter, arg.value().getType()),
1034  DictionaryAttr::get(rewriter.getContext(), {})});
1035  }
1036  }
1037  for (auto res : enumerate(funcType.getResults())) {
1038  std::string resName;
1039  if (auto portNameAttr = funcOp.getResultAttrOfType<StringAttr>(
1040  res.index(), scfToCalyx::sPortNameAttr))
1041  resName = portNameAttr.str();
1042  else
1043  resName = "out" + std::to_string(res.index());
1044  funcOpResultMapping[res.index()] = outPorts.size();
1045  outPorts.push_back(calyx::PortInfo{
1046  rewriter.getStringAttr(resName),
1047  calyx::convIndexType(rewriter, res.value()), calyx::Direction::Output,
1048  DictionaryAttr::get(rewriter.getContext(), {})});
1049  }
1050 
1051  /// We've now recorded all necessary indices. Merge in- and output ports
1052  /// and add the required mandatory component ports.
1053  auto ports = inPorts;
1054  llvm::append_range(ports, outPorts);
1055  calyx::addMandatoryComponentPorts(rewriter, ports);
1056 
1057  /// Create a calyx::ComponentOp corresponding to the to-be-lowered function.
1058  auto compOp = rewriter.create<calyx::ComponentOp>(
1059  funcOp.getLoc(), rewriter.getStringAttr(funcOp.getSymName()), ports);
1060 
1061  std::string funcName = "func_" + funcOp.getSymName().str();
1062  rewriter.updateRootInPlace(funcOp, [&]() { funcOp.setSymName(funcName); });
1063 
1064  /// Mark this component as the toplevel.
1065  compOp->setAttr("toplevel", rewriter.getUnitAttr());
1066 
1067  /// Store the function-to-component mapping.
1068  functionMapping[funcOp] = compOp;
1069  auto *compState = loweringState().getState<ComponentLoweringState>(compOp);
1070  compState->setFuncOpResultMapping(funcOpResultMapping);
1071 
1072  /// Rewrite funcOp SSA argument values to the CompOp arguments.
1073  for (auto &mapping : funcOpArgRewrites)
1074  mapping.getFirst().replaceAllUsesWith(
1075  compOp.getArgument(mapping.getSecond()));
1076 
1077  /// Register external memories
1078  for (auto extMemPortIndices : extMemoryCompPortIndices) {
1079  /// Create a mapping for the in- and output ports using the Calyx memory
1080  /// port structure.
1081  calyx::MemoryPortsImpl extMemPorts;
1082  unsigned inPortsIt = extMemPortIndices.getSecond().first;
1083  unsigned outPortsIt = extMemPortIndices.getSecond().second +
1084  compOp.getInputPortInfo().size();
1085  extMemPorts.readData = compOp.getArgument(inPortsIt++);
1086  extMemPorts.writeDone = compOp.getArgument(inPortsIt);
1087  extMemPorts.writeData = compOp.getArgument(outPortsIt++);
1088  unsigned nAddresses = extMemPortIndices.getFirst()
1089  .getType()
1090  .cast<MemRefType>()
1091  .getShape()
1092  .size();
1093  for (unsigned j = 0; j < nAddresses; ++j)
1094  extMemPorts.addrPorts.push_back(compOp.getArgument(outPortsIt++));
1095  extMemPorts.writeEn = compOp.getArgument(outPortsIt);
1096 
1097  /// Register the external memory ports as a memory interface within the
1098  /// component.
1099  compState->registerMemoryInterface(extMemPortIndices.getFirst(),
1100  calyx::MemoryInterface(extMemPorts));
1101  }
1102 
1103  return success();
1104  }
1105 };
1106 
1107 /// In BuildWhileGroups, a register is created for each iteration argumenet of
1108 /// the while op. These registers are then written to on the while op
1109 /// terminating yield operation alongside before executing the whileOp in the
1110 /// schedule, to set the initial values of the argument registers.
1112  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1113 
1114  LogicalResult
1116  PatternRewriter &rewriter) const override {
1117  LogicalResult res = success();
1118  funcOp.walk([&](Operation *op) {
1119  // Only work on ops that support the ScfWhileOp.
1120  if (!isa<scf::WhileOp>(op))
1121  return WalkResult::advance();
1122 
1123  auto scfWhileOp = cast<scf::WhileOp>(op);
1124  ScfWhileOp whileOp(scfWhileOp);
1125 
1126  getState<ComponentLoweringState>().setUniqueName(whileOp.getOperation(),
1127  "while");
1128 
1129  /// Check for do-while loops.
1130  /// TODO(mortbopet) can we support these? for now, do not support loops
1131  /// where iterargs are changed in the 'before' region. scf.WhileOp also
1132  /// has support for different types of iter_args and return args which we
1133  /// also do not support; iter_args and while return values are placed in
1134  /// the same registers.
1135  for (auto barg :
1136  enumerate(scfWhileOp.getBefore().front().getArguments())) {
1137  auto condOp = scfWhileOp.getConditionOp().getArgs()[barg.index()];
1138  if (barg.value() != condOp) {
1139  res = whileOp.getOperation()->emitError()
1140  << loweringState().irName(barg.value())
1141  << " != " << loweringState().irName(condOp)
1142  << "do-while loops not supported; expected iter-args to "
1143  "remain untransformed in the 'before' region of the "
1144  "scf.while op.";
1145  return WalkResult::interrupt();
1146  }
1147  }
1148 
1149  /// Create iteration argument registers.
1150  /// The iteration argument registers will be referenced:
1151  /// - In the "before" part of the while loop, calculating the conditional,
1152  /// - In the "after" part of the while loop,
1153  /// - Outside the while loop, rewriting the while loop return values.
1154  for (auto arg : enumerate(whileOp.getBodyArgs())) {
1155  std::string name = getState<ComponentLoweringState>()
1156  .getUniqueName(whileOp.getOperation())
1157  .str() +
1158  "_arg" + std::to_string(arg.index());
1159  auto reg =
1160  createRegister(arg.value().getLoc(), rewriter, getComponent(),
1161  arg.value().getType().getIntOrFloatBitWidth(), name);
1162  getState<ComponentLoweringState>().addWhileLoopIterReg(whileOp, reg,
1163  arg.index());
1164  arg.value().replaceAllUsesWith(reg.getOut());
1165 
1166  /// Also replace uses in the "before" region of the while loop
1167  whileOp.getConditionBlock()
1168  ->getArgument(arg.index())
1169  .replaceAllUsesWith(reg.getOut());
1170  }
1171 
1172  /// Create iter args initial value assignment group(s), one per register.
1173  SmallVector<calyx::GroupOp> initGroups;
1174  auto numOperands = whileOp.getOperation()->getNumOperands();
1175  for (size_t i = 0; i < numOperands; ++i) {
1176  auto initGroupOp =
1177  getState<ComponentLoweringState>().buildWhileLoopIterArgAssignments(
1178  rewriter, whileOp,
1179  getState<ComponentLoweringState>().getComponentOp(),
1180  getState<ComponentLoweringState>().getUniqueName(
1181  whileOp.getOperation()) +
1182  "_init_" + std::to_string(i),
1183  whileOp.getOperation()->getOpOperand(i));
1184  initGroups.push_back(initGroupOp);
1185  }
1186 
1187  getState<ComponentLoweringState>().setWhileLoopInitGroups(whileOp,
1188  initGroups);
1189 
1190  return WalkResult::advance();
1191  });
1192  return res;
1193  }
1194 };
1195 
1196 /// In BuildForGroups, a register is created for the iteration argument of
1197 /// the for op. This register is then initialized to the lowerBound of the for
1198 /// loop in a group that executes the for loop.
1200  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1201 
1202  LogicalResult
1204  PatternRewriter &rewriter) const override {
1205  LogicalResult res = success();
1206  funcOp.walk([&](Operation *op) {
1207  // Only work on ops that support the ScfForOp.
1208  if (!isa<scf::ForOp>(op))
1209  return WalkResult::advance();
1210 
1211  auto scfForOp = cast<scf::ForOp>(op);
1212  ScfForOp forOp(scfForOp);
1213 
1214  getState<ComponentLoweringState>().setUniqueName(forOp.getOperation(),
1215  "for");
1216 
1217  // Create a register for the InductionVar, and set that Register as the
1218  // only IterReg for the For Loop
1219  auto inductionVar = forOp.getOperation().getInductionVar();
1220  SmallVector<std::string, 3> inductionVarIdentifiers = {
1221  getState<ComponentLoweringState>()
1222  .getUniqueName(forOp.getOperation())
1223  .str(),
1224  "induction", "var"};
1225  std::string name = llvm::join(inductionVarIdentifiers, "_");
1226  auto reg =
1227  createRegister(inductionVar.getLoc(), rewriter, getComponent(),
1228  inductionVar.getType().getIntOrFloatBitWidth(), name);
1229  getState<ComponentLoweringState>().addForLoopIterReg(forOp, reg, 0);
1230  inductionVar.replaceAllUsesWith(reg.getOut());
1231 
1232  // Create InitGroup that sets the InductionVar to LowerBound
1233  calyx::ComponentOp componentOp =
1234  getState<ComponentLoweringState>().getComponentOp();
1235  SmallVector<calyx::GroupOp> initGroups;
1236  SmallVector<std::string, 4> groupIdentifiers = {
1237  "init",
1238  getState<ComponentLoweringState>()
1239  .getUniqueName(forOp.getOperation())
1240  .str(),
1241  "induction", "var"};
1242  std::string groupName = llvm::join(groupIdentifiers, "_");
1243  auto groupOp = calyx::createGroup<calyx::GroupOp>(
1244  rewriter, componentOp, forOp.getLoc(), groupName);
1245  buildAssignmentsForRegisterWrite(rewriter, groupOp, componentOp, reg,
1246  forOp.getOperation().getLowerBound());
1247  initGroups.push_back(groupOp);
1248  getState<ComponentLoweringState>().setForLoopInitGroups(forOp,
1249  initGroups);
1250 
1251  return WalkResult::advance();
1252  });
1253  return res;
1254  }
1255 };
1256 
1257 /// Builds a control schedule by traversing the CFG of the function and
1258 /// associating this with the previously created groups.
1259 /// For simplicity, the generated control flow is expanded for all possible
1260 /// paths in the input DAG. This elaborated control flow is later reduced in
1261 /// the runControlFlowSimplification passes.
1263  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1264 
1265  LogicalResult
1267  PatternRewriter &rewriter) const override {
1268  auto *entryBlock = &funcOp.getBlocks().front();
1269  rewriter.setInsertionPointToStart(
1270  getComponent().getControlOp().getBodyBlock());
1271  auto topLevelSeqOp = rewriter.create<calyx::SeqOp>(funcOp.getLoc());
1272  DenseSet<Block *> path;
1273  return buildCFGControl(path, rewriter, topLevelSeqOp.getBodyBlock(),
1274  nullptr, entryBlock);
1275  }
1276 
1277 private:
1278  /// Sequentially schedules the groups that registered themselves with
1279  /// 'block'.
1280  LogicalResult scheduleBasicBlock(PatternRewriter &rewriter,
1281  const DenseSet<Block *> &path,
1282  mlir::Block *parentCtrlBlock,
1283  mlir::Block *block) const {
1284  auto compBlockScheduleables =
1285  getState<ComponentLoweringState>().getBlockScheduleables(block);
1286  auto loc = block->front().getLoc();
1287 
1288  if (compBlockScheduleables.size() > 1) {
1289  auto seqOp = rewriter.create<calyx::SeqOp>(loc);
1290  parentCtrlBlock = seqOp.getBodyBlock();
1291  }
1292 
1293  for (auto &group : compBlockScheduleables) {
1294  rewriter.setInsertionPointToEnd(parentCtrlBlock);
1295  if (auto groupPtr = std::get_if<calyx::GroupOp>(&group); groupPtr) {
1296  rewriter.create<calyx::EnableOp>(groupPtr->getLoc(),
1297  groupPtr->getSymName());
1298  } else if (auto whileSchedPtr = std::get_if<WhileScheduleable>(&group);
1299  whileSchedPtr) {
1300  auto &whileOp = whileSchedPtr->whileOp;
1301 
1302  auto whileCtrlOp = buildWhileCtrlOp(
1303  whileOp,
1304  getState<ComponentLoweringState>().getWhileLoopInitGroups(whileOp),
1305  rewriter);
1306  rewriter.setInsertionPointToEnd(whileCtrlOp.getBodyBlock());
1307  auto whileBodyOp =
1308  rewriter.create<calyx::SeqOp>(whileOp.getOperation()->getLoc());
1309  auto *whileBodyOpBlock = whileBodyOp.getBodyBlock();
1310 
1311  /// Only schedule the 'after' block. The 'before' block is
1312  /// implicitly scheduled when evaluating the while condition.
1313  LogicalResult res = buildCFGControl(path, rewriter, whileBodyOpBlock,
1314  block, whileOp.getBodyBlock());
1315 
1316  // Insert loop-latch at the end of the while group
1317  rewriter.setInsertionPointToEnd(whileBodyOpBlock);
1318  calyx::GroupOp whileLatchGroup =
1319  getState<ComponentLoweringState>().getWhileLoopLatchGroup(whileOp);
1320  rewriter.create<calyx::EnableOp>(whileLatchGroup.getLoc(),
1321  whileLatchGroup.getName());
1322 
1323  if (res.failed())
1324  return res;
1325  } else if (auto *forSchedPtr = std::get_if<ForScheduleable>(&group);
1326  forSchedPtr) {
1327  auto forOp = forSchedPtr->forOp;
1328 
1329  auto forCtrlOp = buildForCtrlOp(
1330  forOp,
1331  getState<ComponentLoweringState>().getForLoopInitGroups(forOp),
1332  forSchedPtr->bound, rewriter);
1333  rewriter.setInsertionPointToEnd(forCtrlOp.getBodyBlock());
1334  auto forBodyOp =
1335  rewriter.create<calyx::SeqOp>(forOp.getOperation()->getLoc());
1336  auto *forBodyOpBlock = forBodyOp.getBodyBlock();
1337 
1338  // Schedule the body of the for loop.
1339  LogicalResult res = buildCFGControl(path, rewriter, forBodyOpBlock,
1340  block, forOp.getBodyBlock());
1341 
1342  // Insert loop-latch at the end of the while group.
1343  rewriter.setInsertionPointToEnd(forBodyOpBlock);
1344  calyx::GroupOp forLatchGroup =
1345  getState<ComponentLoweringState>().getForLoopLatchGroup(forOp);
1346  rewriter.create<calyx::EnableOp>(forLatchGroup.getLoc(),
1347  forLatchGroup.getName());
1348  if (res.failed())
1349  return res;
1350  } else if (auto *callSchedPtr = std::get_if<CallScheduleable>(&group)) {
1351  auto instanceOp = callSchedPtr->instanceOp;
1352  OpBuilder::InsertionGuard g(rewriter);
1353  auto callBody = rewriter.create<calyx::SeqOp>(instanceOp.getLoc());
1354  rewriter.setInsertionPointToStart(callBody.getBodyBlock());
1355  std::string initGroupName = "init_" + instanceOp.getSymName().str();
1356  rewriter.create<calyx::EnableOp>(instanceOp.getLoc(), initGroupName);
1357  SmallVector<Value, 4> instancePorts;
1358  auto inputPorts = callSchedPtr->callOp.getOperands();
1359  llvm::copy(instanceOp.getResults().take_front(inputPorts.size()),
1360  std::back_inserter(instancePorts));
1361  rewriter.create<calyx::InvokeOp>(
1362  instanceOp.getLoc(), instanceOp.getSymName(), instancePorts,
1363  inputPorts, ArrayAttr::get(rewriter.getContext(), {}),
1364  ArrayAttr::get(rewriter.getContext(), {}));
1365  } else
1366  llvm_unreachable("Unknown scheduleable");
1367  }
1368  return success();
1369  }
1370 
1371  /// Schedules a block by inserting a branch argument assignment block (if any)
1372  /// before recursing into the scheduling of the block innards.
1373  /// Blocks 'from' and 'to' refer to blocks in the source program.
1374  /// parentCtrlBlock refers to the control block wherein control operations are
1375  /// to be inserted.
1376  LogicalResult schedulePath(PatternRewriter &rewriter,
1377  const DenseSet<Block *> &path, Location loc,
1378  Block *from, Block *to,
1379  Block *parentCtrlBlock) const {
1380  /// Schedule any registered block arguments to be executed before the body
1381  /// of the branch.
1382  rewriter.setInsertionPointToEnd(parentCtrlBlock);
1383  auto preSeqOp = rewriter.create<calyx::SeqOp>(loc);
1384  rewriter.setInsertionPointToEnd(preSeqOp.getBodyBlock());
1385  for (auto barg :
1386  getState<ComponentLoweringState>().getBlockArgGroups(from, to))
1387  rewriter.create<calyx::EnableOp>(barg.getLoc(), barg.getSymName());
1388 
1389  return buildCFGControl(path, rewriter, parentCtrlBlock, from, to);
1390  }
1391 
1392  LogicalResult buildCFGControl(DenseSet<Block *> path,
1393  PatternRewriter &rewriter,
1394  mlir::Block *parentCtrlBlock,
1395  mlir::Block *preBlock,
1396  mlir::Block *block) const {
1397  if (path.count(block) != 0)
1398  return preBlock->getTerminator()->emitError()
1399  << "CFG backedge detected. Loops must be raised to 'scf.while' or "
1400  "'scf.for' operations.";
1401 
1402  rewriter.setInsertionPointToEnd(parentCtrlBlock);
1403  LogicalResult bbSchedResult =
1404  scheduleBasicBlock(rewriter, path, parentCtrlBlock, block);
1405  if (bbSchedResult.failed())
1406  return bbSchedResult;
1407 
1408  path.insert(block);
1409  auto successors = block->getSuccessors();
1410  auto nSuccessors = successors.size();
1411  if (nSuccessors > 0) {
1412  auto brOp = dyn_cast<BranchOpInterface>(block->getTerminator());
1413  assert(brOp);
1414  if (nSuccessors > 1) {
1415  /// TODO(mortbopet): we could choose to support ie. std.switch, but it
1416  /// would probably be easier to just require it to be lowered
1417  /// beforehand.
1418  assert(nSuccessors == 2 &&
1419  "only conditional branches supported for now...");
1420  /// Wrap each branch inside an if/else.
1421  auto cond = brOp->getOperand(0);
1422  auto condGroup = getState<ComponentLoweringState>()
1423  .getEvaluatingGroup<calyx::CombGroupOp>(cond);
1424  auto symbolAttr = FlatSymbolRefAttr::get(
1425  StringAttr::get(getContext(), condGroup.getSymName()));
1426 
1427  auto ifOp = rewriter.create<calyx::IfOp>(
1428  brOp->getLoc(), cond, symbolAttr, /*initializeElseBody=*/true);
1429  rewriter.setInsertionPointToStart(ifOp.getThenBody());
1430  auto thenSeqOp = rewriter.create<calyx::SeqOp>(brOp.getLoc());
1431  rewriter.setInsertionPointToStart(ifOp.getElseBody());
1432  auto elseSeqOp = rewriter.create<calyx::SeqOp>(brOp.getLoc());
1433 
1434  bool trueBrSchedSuccess =
1435  schedulePath(rewriter, path, brOp.getLoc(), block, successors[0],
1436  thenSeqOp.getBodyBlock())
1437  .succeeded();
1438  bool falseBrSchedSuccess = true;
1439  if (trueBrSchedSuccess) {
1440  falseBrSchedSuccess =
1441  schedulePath(rewriter, path, brOp.getLoc(), block, successors[1],
1442  elseSeqOp.getBodyBlock())
1443  .succeeded();
1444  }
1445 
1446  return success(trueBrSchedSuccess && falseBrSchedSuccess);
1447  } else {
1448  /// Schedule sequentially within the current parent control block.
1449  return schedulePath(rewriter, path, brOp.getLoc(), block,
1450  successors.front(), parentCtrlBlock);
1451  }
1452  }
1453  return success();
1454  }
1455 
1456  // Insert a Par of initGroups at Location loc. Used as helper for
1457  // `buildWhileCtrlOp` and `buildForCtrlOp`.
1458  void
1459  insertParInitGroups(PatternRewriter &rewriter, Location loc,
1460  const SmallVector<calyx::GroupOp> &initGroups) const {
1461  PatternRewriter::InsertionGuard g(rewriter);
1462  auto parOp = rewriter.create<calyx::ParOp>(loc);
1463  rewriter.setInsertionPointToStart(parOp.getBodyBlock());
1464  for (calyx::GroupOp group : initGroups)
1465  rewriter.create<calyx::EnableOp>(group.getLoc(), group.getName());
1466  }
1467 
1468  calyx::WhileOp buildWhileCtrlOp(ScfWhileOp whileOp,
1469  SmallVector<calyx::GroupOp> initGroups,
1470  PatternRewriter &rewriter) const {
1471  Location loc = whileOp.getLoc();
1472  /// Insert while iter arg initialization group(s). Emit a
1473  /// parallel group to assign one or more registers all at once.
1474  insertParInitGroups(rewriter, loc, initGroups);
1475 
1476  /// Insert the while op itself.
1477  auto cond = whileOp.getConditionValue();
1478  auto condGroup = getState<ComponentLoweringState>()
1479  .getEvaluatingGroup<calyx::CombGroupOp>(cond);
1480  auto symbolAttr = FlatSymbolRefAttr::get(
1481  StringAttr::get(getContext(), condGroup.getSymName()));
1482  return rewriter.create<calyx::WhileOp>(loc, cond, symbolAttr);
1483  }
1484 
1485  calyx::RepeatOp buildForCtrlOp(ScfForOp forOp,
1486  SmallVector<calyx::GroupOp> const &initGroups,
1487  uint64_t bound,
1488  PatternRewriter &rewriter) const {
1489  Location loc = forOp.getLoc();
1490  // Insert for iter arg initialization group(s). Emit a
1491  // parallel group to assign one or more registers all at once.
1492  insertParInitGroups(rewriter, loc, initGroups);
1493 
1494  // Insert the repeatOp that corresponds to the For loop.
1495  return rewriter.create<calyx::RepeatOp>(loc, bound);
1496  }
1497 };
1498 
1499 /// LateSSAReplacement contains various functions for replacing SSA values that
1500 /// were not replaced during op construction.
1502  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1503 
1504  LogicalResult partiallyLowerFuncToComp(FuncOp funcOp,
1505  PatternRewriter &) const override {
1506  funcOp.walk([&](scf::WhileOp op) {
1507  /// The yielded values returned from the while op will be present in the
1508  /// iterargs registers post execution of the loop.
1509  /// This is done now, as opposed to during BuildWhileGroups since if the
1510  /// results of the whileOp were replaced before
1511  /// BuildOpGroups/BuildControl, the whileOp would get dead-code
1512  /// eliminated.
1513  ScfWhileOp whileOp(op);
1514  for (auto res :
1515  getState<ComponentLoweringState>().getWhileLoopIterRegs(whileOp))
1516  whileOp.getOperation()->getResults()[res.first].replaceAllUsesWith(
1517  res.second.getOut());
1518  });
1519 
1520  funcOp.walk([&](memref::LoadOp loadOp) {
1521  if (calyx::singleLoadFromMemory(loadOp)) {
1522  /// In buildOpGroups we did not replace loadOp's results, to ensure a
1523  /// link between evaluating groups (which fix the input addresses of a
1524  /// memory op) and a readData result. Now, we may replace these SSA
1525  /// values with their memoryOp readData output.
1526  loadOp.getResult().replaceAllUsesWith(
1527  getState<ComponentLoweringState>()
1528  .getMemoryInterface(loadOp.getMemref())
1529  .readData());
1530  }
1531  });
1532 
1533  return success();
1534  }
1535 };
1536 
1537 /// Erases FuncOp operations.
1539  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1540 
1541  LogicalResult matchAndRewrite(FuncOp funcOp,
1542  PatternRewriter &rewriter) const override {
1543  rewriter.eraseOp(funcOp);
1544  return success();
1545  }
1546 
1547  LogicalResult
1549  PatternRewriter &rewriter) const override {
1550  return success();
1551  }
1552 };
1553 
1554 //===----------------------------------------------------------------------===//
1555 // Pass driver
1556 //===----------------------------------------------------------------------===//
1557 class SCFToCalyxPass : public SCFToCalyxBase<SCFToCalyxPass> {
1558 public:
1560  : SCFToCalyxBase<SCFToCalyxPass>(), partialPatternRes(success()) {}
1561  void runOnOperation() override;
1562 
1563  LogicalResult setTopLevelFunction(mlir::ModuleOp moduleOp,
1564  std::string &topLevelFunction) {
1565  if (!topLevelFunctionOpt.empty()) {
1566  if (SymbolTable::lookupSymbolIn(moduleOp, topLevelFunctionOpt) ==
1567  nullptr) {
1568  moduleOp.emitError() << "Top level function '" << topLevelFunctionOpt
1569  << "' not found in module.";
1570  return failure();
1571  }
1572  topLevelFunction = topLevelFunctionOpt;
1573  } else {
1574  /// No top level function set; infer top level if the module only contains
1575  /// a single function, else, throw error.
1576  auto funcOps = moduleOp.getOps<FuncOp>();
1577  if (std::distance(funcOps.begin(), funcOps.end()) == 1)
1578  topLevelFunction = (*funcOps.begin()).getSymName().str();
1579  else {
1580  moduleOp.emitError()
1581  << "Module contains multiple functions, but no top level "
1582  "function was set. Please see --top-level-function";
1583  return failure();
1584  }
1585  }
1586  return success();
1587  }
1588 
1590  enum class Strategy { Once, Greedy };
1591  RewritePatternSet pattern;
1593  };
1594 
1595  //// Labels the entry point of a Calyx program.
1596  /// Furthermore, this function performs validation on the input function,
1597  /// to ensure that we've implemented the capabilities necessary to convert
1598  /// it.
1599  LogicalResult labelEntryPoint(StringRef topLevelFunction) {
1600  // Program legalization - the partial conversion driver will not run
1601  // unless some pattern is provided - provide a dummy pattern.
1602  struct DummyPattern : public OpRewritePattern<mlir::ModuleOp> {
1603  using OpRewritePattern::OpRewritePattern;
1604  LogicalResult matchAndRewrite(mlir::ModuleOp,
1605  PatternRewriter &) const override {
1606  return failure();
1607  }
1608  };
1609 
1610  ConversionTarget target(getContext());
1611  target.addLegalDialect<calyx::CalyxDialect>();
1612  target.addLegalDialect<scf::SCFDialect>();
1613  target.addIllegalDialect<hw::HWDialect>();
1614  target.addIllegalDialect<comb::CombDialect>();
1615 
1616  // Only accept std operations which we've added lowerings for
1617  target.addIllegalDialect<FuncDialect>();
1618  target.addIllegalDialect<ArithDialect>();
1619  target.addLegalOp<AddIOp, SelectOp, SubIOp, CmpIOp, ShLIOp, ShRUIOp,
1620  ShRSIOp, AndIOp, XOrIOp, OrIOp, ExtUIOp, TruncIOp,
1621  CondBranchOp, BranchOp, MulIOp, DivUIOp, DivSIOp, RemUIOp,
1622  RemSIOp, ReturnOp, arith::ConstantOp, IndexCastOp, FuncOp,
1623  ExtSIOp, CallOp>();
1624 
1625  RewritePatternSet legalizePatterns(&getContext());
1626  legalizePatterns.add<DummyPattern>(&getContext());
1627  DenseSet<Operation *> legalizedOps;
1628  if (applyPartialConversion(getOperation(), target,
1629  std::move(legalizePatterns))
1630  .failed())
1631  return failure();
1632 
1633  // Program conversion
1634  return calyx::applyModuleOpConversion(getOperation(), topLevelFunction);
1635  }
1636 
1637  /// 'Once' patterns are expected to take an additional LogicalResult&
1638  /// argument, to forward their result state (greedyPatternRewriteDriver
1639  /// results are skipped for Once patterns).
1640  template <typename TPattern, typename... PatternArgs>
1641  void addOncePattern(SmallVectorImpl<LoweringPattern> &patterns,
1642  PatternArgs &&...args) {
1643  RewritePatternSet ps(&getContext());
1644  ps.add<TPattern>(&getContext(), partialPatternRes, args...);
1645  patterns.push_back(
1646  LoweringPattern{std::move(ps), LoweringPattern::Strategy::Once});
1647  }
1648 
1649  template <typename TPattern, typename... PatternArgs>
1650  void addGreedyPattern(SmallVectorImpl<LoweringPattern> &patterns,
1651  PatternArgs &&...args) {
1652  RewritePatternSet ps(&getContext());
1653  ps.add<TPattern>(&getContext(), args...);
1654  patterns.push_back(
1655  LoweringPattern{std::move(ps), LoweringPattern::Strategy::Greedy});
1656  }
1657 
1658  LogicalResult runPartialPattern(RewritePatternSet &pattern, bool runOnce) {
1659  assert(pattern.getNativePatterns().size() == 1 &&
1660  "Should only apply 1 partial lowering pattern at once");
1661 
1662  // During component creation, the function body is inlined into the
1663  // component body for further processing. However, proper control flow
1664  // will only be established later in the conversion process, so ensure
1665  // that rewriter optimizations (especially DCE) are disabled.
1666  GreedyRewriteConfig config;
1667  config.enableRegionSimplification = false;
1668  if (runOnce)
1669  config.maxIterations = 1;
1670 
1671  /// Can't return applyPatternsAndFoldGreedily. Root isn't
1672  /// necessarily erased so it will always return failed(). Instead,
1673  /// forward the 'succeeded' value from PartialLoweringPatternBase.
1674  (void)applyPatternsAndFoldGreedily(getOperation(), std::move(pattern),
1675  config);
1676  return partialPatternRes;
1677  }
1678 
1679 private:
1680  LogicalResult partialPatternRes;
1681  std::shared_ptr<calyx::CalyxLoweringState> loweringState = nullptr;
1682 };
1683 
1684 void SCFToCalyxPass::runOnOperation() {
1685  // Clear internal state. See https://github.com/llvm/circt/issues/3235
1686  loweringState.reset();
1687  partialPatternRes = LogicalResult::failure();
1688 
1689  std::string topLevelFunction;
1690  if (failed(setTopLevelFunction(getOperation(), topLevelFunction))) {
1691  signalPassFailure();
1692  return;
1693  }
1694 
1695  /// Start conversion
1696  if (failed(labelEntryPoint(topLevelFunction))) {
1697  signalPassFailure();
1698  return;
1699  }
1700  loweringState = std::make_shared<calyx::CalyxLoweringState>(getOperation(),
1701  topLevelFunction);
1702 
1703  /// --------------------------------------------------------------------------
1704  /// If you are a developer, it may be helpful to add a
1705  /// 'getOperation()->dump()' call after the execution of each stage to
1706  /// view the transformations that's going on.
1707  /// --------------------------------------------------------------------------
1708 
1709  /// A mapping is maintained between a function operation and its corresponding
1710  /// Calyx component.
1711  DenseMap<FuncOp, calyx::ComponentOp> funcMap;
1712  SmallVector<LoweringPattern, 8> loweringPatterns;
1713  calyx::PatternApplicationState patternState;
1714 
1715  /// Creates a new Calyx component for each FuncOp in the inpurt module.
1716  addOncePattern<FuncOpConversion>(loweringPatterns, patternState, funcMap,
1717  *loweringState);
1718 
1719  /// This pass inlines scf.ExecuteRegionOp's by adding control-flow.
1720  addGreedyPattern<InlineExecuteRegionOpPattern>(loweringPatterns);
1721 
1722  /// This pattern converts all index typed values to an i32 integer.
1723  addOncePattern<calyx::ConvertIndexTypes>(loweringPatterns, patternState,
1724  funcMap, *loweringState);
1725 
1726  /// This pattern creates registers for all basic-block arguments.
1727  addOncePattern<calyx::BuildBasicBlockRegs>(loweringPatterns, patternState,
1728  funcMap, *loweringState);
1729 
1730  addOncePattern<calyx::BuildCallInstance>(loweringPatterns, patternState,
1731  funcMap, *loweringState);
1732 
1733  /// This pattern creates registers for the function return values.
1734  addOncePattern<calyx::BuildReturnRegs>(loweringPatterns, patternState,
1735  funcMap, *loweringState);
1736 
1737  /// This pattern creates registers for iteration arguments of scf.while
1738  /// operations. Additionally, creates a group for assigning the initial
1739  /// value of the iteration argument registers.
1740  addOncePattern<BuildWhileGroups>(loweringPatterns, patternState, funcMap,
1741  *loweringState);
1742 
1743  /// This pattern creates registers for iteration arguments of scf.for
1744  /// operations. Additionally, creates a group for assigning the initial
1745  /// value of the iteration argument registers.
1746  addOncePattern<BuildForGroups>(loweringPatterns, patternState, funcMap,
1747  *loweringState);
1748 
1749  /// This pattern converts operations within basic blocks to Calyx library
1750  /// operators. Combinational operations are assigned inside a
1751  /// calyx::CombGroupOp, and sequential inside calyx::GroupOps.
1752  /// Sequential groups are registered with the Block* of which the operation
1753  /// originated from. This is used during control schedule generation. By
1754  /// having a distinct group for each operation, groups are analogous to SSA
1755  /// values in the source program.
1756  addOncePattern<BuildOpGroups>(loweringPatterns, patternState, funcMap,
1757  *loweringState);
1758 
1759  /// This pattern traverses the CFG of the program and generates a control
1760  /// schedule based on the calyx::GroupOp's which were registered for each
1761  /// basic block in the source function.
1762  addOncePattern<BuildControl>(loweringPatterns, patternState, funcMap,
1763  *loweringState);
1764 
1765  /// This pass recursively inlines use-def chains of combinational logic (from
1766  /// non-stateful groups) into groups referenced in the control schedule.
1767  addOncePattern<calyx::InlineCombGroups>(loweringPatterns, patternState,
1768  *loweringState);
1769 
1770  /// This pattern performs various SSA replacements that must be done
1771  /// after control generation.
1772  addOncePattern<LateSSAReplacement>(loweringPatterns, patternState, funcMap,
1773  *loweringState);
1774 
1775  /// Eliminate any unused combinational groups. This is done before
1776  /// calyx::RewriteMemoryAccesses to avoid inferring slice components for
1777  /// groups that will be removed.
1778  addGreedyPattern<calyx::EliminateUnusedCombGroups>(loweringPatterns);
1779 
1780  /// This pattern rewrites accesses to memories which are too wide due to
1781  /// index types being converted to a fixed-width integer type.
1782  addOncePattern<calyx::RewriteMemoryAccesses>(loweringPatterns, patternState,
1783  *loweringState);
1784 
1785  /// This pattern removes the source FuncOp which has now been converted into
1786  /// a Calyx component.
1787  addOncePattern<CleanupFuncOps>(loweringPatterns, patternState, funcMap,
1788  *loweringState);
1789 
1790  /// Sequentially apply each lowering pattern.
1791  for (auto &pat : loweringPatterns) {
1792  LogicalResult partialPatternRes = runPartialPattern(
1793  pat.pattern,
1794  /*runOnce=*/pat.strategy == LoweringPattern::Strategy::Once);
1795  if (succeeded(partialPatternRes))
1796  continue;
1797  signalPassFailure();
1798  return;
1799  }
1800 
1801  //===----------------------------------------------------------------------===//
1802  // Cleanup patterns
1803  //===----------------------------------------------------------------------===//
1804  RewritePatternSet cleanupPatterns(&getContext());
1805  cleanupPatterns.add<calyx::MultipleGroupDonePattern,
1806  calyx::NonTerminatingGroupDonePattern>(&getContext());
1807  if (failed(applyPatternsAndFoldGreedily(getOperation(),
1808  std::move(cleanupPatterns)))) {
1809  signalPassFailure();
1810  return;
1811  }
1812 
1813  if (ciderSourceLocationMetadata) {
1814  // Debugging information for the Cider debugger.
1815  // Reference: https://docs.calyxir.org/debug/cider.html
1816  SmallVector<Attribute, 16> sourceLocations;
1817  getOperation()->walk([&](calyx::ComponentOp component) {
1818  return getCiderSourceLocationMetadata(component, sourceLocations);
1819  });
1820 
1821  MLIRContext *context = getOperation()->getContext();
1822  getOperation()->setAttr("calyx.metadata",
1823  ArrayAttr::get(context, sourceLocations));
1824  }
1825 }
1826 
1827 } // namespace scftocalyx
1828 
1829 //===----------------------------------------------------------------------===//
1830 // Pass initialization
1831 //===----------------------------------------------------------------------===//
1832 
1833 std::unique_ptr<OperationPass<ModuleOp>> createSCFToCalyxPass() {
1834  return std::make_unique<scftocalyx::SCFToCalyxPass>();
1835 }
1836 
1837 } // namespace circt
lowerAnnotationsNoRefTypePorts FirtoolPreserveValuesMode value
Definition: Firtool.cpp:95
assert(baseType &&"element must be base type")
int32_t width
Definition: FIRRTL.cpp:27
@ Input
Definition: HW.h:32
@ Output
Definition: HW.h:32
Builder builder
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
Iterate through the operations of a source function and instantiate components or primitives based on...
Definition: SCFToCalyx.cpp:198
TGroupOp createGroupForOp(PatternRewriter &rewriter, Operation *op) const
Creates a group named by the basic block which the input op resides in.
Definition: SCFToCalyx.cpp:327
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:320
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:384
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:276
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
Definition: SCFToCalyx.cpp:202
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:339
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:186
ComponentLoweringState(calyx::ComponentOp component)
Definition: SCFToCalyx.cpp:188
void setForLoopInitGroups(ScfForOp op, SmallVector< calyx::GroupOp > groups)
Definition: SCFToCalyx.cpp:175
calyx::GroupOp buildForLoopIterArgAssignments(OpBuilder &builder, ScfForOp op, calyx::ComponentOp componentOp, Twine uniqueSuffix, MutableArrayRef< OpOperand > ops)
Definition: SCFToCalyx.cpp:154
void setForLoopLatchGroup(ScfForOp op, calyx::GroupOp group)
Definition: SCFToCalyx.cpp:169
SmallVector< calyx::GroupOp > getForLoopInitGroups(ScfForOp op)
Definition: SCFToCalyx.cpp:151
void addForLoopIterReg(ScfForOp op, calyx::RegisterOp reg, unsigned idx)
Definition: SCFToCalyx.cpp:160
calyx::GroupOp getForLoopLatchGroup(ScfForOp op)
Definition: SCFToCalyx.cpp:172
calyx::RegisterOp getForLoopIterReg(ScfForOp op, unsigned idx)
Definition: SCFToCalyx.cpp:166
const DenseMap< unsigned, calyx::RegisterOp > & getForLoopIterRegs(ScfForOp op)
Definition: SCFToCalyx.cpp:163
Inlines Calyx ExecuteRegionOp operations within their parent blocks.
Definition: SCFToCalyx.cpp:941
LogicalResult matchAndRewrite(scf::ExecuteRegionOp execOp, PatternRewriter &rewriter) const override
Definition: SCFToCalyx.cpp:944
LateSSAReplacement contains various functions for replacing SSA values that were not replaced during ...
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &) const override
LogicalResult labelEntryPoint(StringRef topLevelFunction)
Labels the entry point of a Calyx program.
LogicalResult runPartialPattern(RewritePatternSet &pattern, bool runOnce)
LogicalResult setTopLevelFunction(mlir::ModuleOp moduleOp, std::string &topLevelFunction)
void addGreedyPattern(SmallVectorImpl< LoweringPattern > &patterns, PatternArgs &&...args)
void addOncePattern(SmallVectorImpl< LoweringPattern > &patterns, PatternArgs &&...args)
'Once' patterns are expected to take an additional LogicalResult& argument, to forward their result s...
std::optional< int64_t > getBound() override
Definition: SCFToCalyx.cpp:83
Block * getBodyBlock() override
Definition: SCFToCalyx.cpp:79
Block::BlockArgListType getBodyArgs() override
Definition: SCFToCalyx.cpp:75
ScfWhileOp(scf::WhileOp op)
Definition: SCFToCalyx.cpp:51
Block::BlockArgListType getBodyArgs() override
Definition: SCFToCalyx.cpp:54
Block * getConditionBlock() override
Definition: SCFToCalyx.cpp:60
std::optional< int64_t > getBound() override
Definition: SCFToCalyx.cpp:68
Block * getBodyBlock() override
Definition: SCFToCalyx.cpp:58
Value getConditionValue() override
Definition: SCFToCalyx.cpp:64
calyx::GroupOp buildWhileLoopIterArgAssignments(OpBuilder &builder, ScfWhileOp op, calyx::ComponentOp componentOp, Twine uniqueSuffix, MutableArrayRef< OpOperand > ops)
Definition: SCFToCalyx.cpp:123
void setWhileLoopInitGroups(ScfWhileOp op, SmallVector< calyx::GroupOp > groups)
Definition: SCFToCalyx.cpp:142
SmallVector< calyx::GroupOp > getWhileLoopInitGroups(ScfWhileOp op)
Definition: SCFToCalyx.cpp:120
void addWhileLoopIterReg(ScfWhileOp op, calyx::RegisterOp reg, unsigned idx)
Definition: SCFToCalyx.cpp:129
const DenseMap< unsigned, calyx::RegisterOp > & getWhileLoopIterRegs(ScfWhileOp op)
Definition: SCFToCalyx.cpp:133
void setWhileLoopLatchGroup(ScfWhileOp op, calyx::GroupOp group)
Definition: SCFToCalyx.cpp:136
calyx::GroupOp getWhileLoopLatchGroup(ScfWhileOp op)
Definition: SCFToCalyx.cpp:139
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition: CalyxOps.cpp:53
void addMandatoryComponentPorts(PatternRewriter &rewriter, SmallVectorImpl< calyx::PortInfo > &ports)
void appendPortsForExternalMemref(PatternRewriter &rewriter, StringRef memName, Value memref, unsigned memoryID, SmallVectorImpl< calyx::PortInfo > &inPorts, SmallVectorImpl< calyx::PortInfo > &outPorts)
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...
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:26
std::variant< calyx::GroupOp, WhileScheduleable, ForScheduleable, CallScheduleable > Scheduleable
A variant of types representing scheduleable operations.
Definition: SCFToCalyx.cpp:115
static LogicalResult buildAllocOp(ComponentLoweringState &componentState, PatternRewriter &rewriter, TAllocOp allocOp)
Definition: SCFToCalyx.cpp:571
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
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:20
std::optional< Value > writeEn
std::optional< Value > writeData
std::optional< Value > readData
std::optional< Value > writeDone
SmallVector< Value > addrPorts
When building groups which contain accesses to multiple sequential components, a group_done op is cre...
GroupDoneOp's are terminator operations and should therefore be the last operator in a group.
This holds information about the port for either a Component or Cell.
Definition: CalyxOps.h:78
calyx::InstanceOp instanceOp
Instance for invoking.
Definition: SCFToCalyx.cpp:108
ScfForOp forOp
For operation to schedule.
Definition: SCFToCalyx.cpp:101
Creates a new Calyx component for each FuncOp in the program.
Definition: SCFToCalyx.cpp:985
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
Definition: SCFToCalyx.cpp:989
ScfWhileOp whileOp
While operation to schedule.
Definition: SCFToCalyx.cpp:96