CIRCT  19.0.0git
LoopScheduleToCalyx.cpp
Go to the documentation of this file.
1 //=== LoopScheduleToCalyx.cpp - LoopSchedule to Calyx pass entry point-----===//
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 LoopSchedule to Calyx conversion pass implementation.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "../PassDetail.h"
19 #include "circt/Dialect/HW/HWOps.h"
21 #include "mlir/Conversion/LLVMCommon/ConversionTarget.h"
22 #include "mlir/Conversion/LLVMCommon/Pattern.h"
23 #include "mlir/Dialect/Arith/IR/Arith.h"
24 #include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
25 #include "mlir/Dialect/Func/IR/FuncOps.h"
26 #include "mlir/Dialect/MemRef/IR/MemRef.h"
27 #include "mlir/IR/AsmState.h"
28 #include "mlir/IR/Matchers.h"
29 #include "mlir/Transforms/GreedyPatternRewriteDriver.h"
30 #include "llvm/ADT/TypeSwitch.h"
31 
32 #include <variant>
33 
34 using namespace llvm;
35 using namespace mlir;
36 using namespace mlir::arith;
37 using namespace mlir::cf;
38 using namespace mlir::func;
39 using namespace circt::loopschedule;
40 
41 namespace circt {
42 namespace pipelinetocalyx {
43 
44 //===----------------------------------------------------------------------===//
45 // Utility types
46 //===----------------------------------------------------------------------===//
47 
48 class PipelineWhileOp : public calyx::WhileOpInterface<LoopSchedulePipelineOp> {
49 public:
50  explicit PipelineWhileOp(LoopSchedulePipelineOp op)
51  : calyx::WhileOpInterface<LoopSchedulePipelineOp>(op) {}
52 
53  Block::BlockArgListType getBodyArgs() override {
54  return getOperation().getStagesBlock().getArguments();
55  }
56 
57  Block *getBodyBlock() override { return &getOperation().getStagesBlock(); }
58 
59  Block *getConditionBlock() override { return &getOperation().getCondBlock(); }
60 
61  Value getConditionValue() override {
62  return getOperation().getCondBlock().getTerminator()->getOperand(0);
63  }
64 
65  std::optional<int64_t> getBound() override {
66  return getOperation().getTripCount();
67  }
68 };
69 
70 //===----------------------------------------------------------------------===//
71 // Lowering state classes
72 //===----------------------------------------------------------------------===//
73 
75  /// While operation to schedule.
77  /// The group(s) to schedule before the while operation These groups should
78  /// set the initial value(s) of the loop init_args register(s).
79  SmallVector<calyx::GroupOp> initGroups;
80 };
81 
82 /// A variant of types representing scheduleable operations.
83 using Scheduleable = std::variant<calyx::GroupOp, PipelineScheduleable>;
84 
85 /// Holds additional information required for scheduling Pipeline pipelines.
86 class PipelineScheduler : public calyx::SchedulerInterface<Scheduleable> {
87 public:
88  /// Registers operations that may be used in a pipeline, but does not produce
89  /// a value to be used in a further stage.
90  void registerNonPipelineOperations(Operation *op,
91  calyx::GroupInterface group) {
92  operationToGroup[op] = group;
93  }
94 
95  /// Returns the group registered for this non-pipelined value, and None
96  /// otherwise.
97  template <typename TGroupOp = calyx::GroupInterface>
98  std::optional<TGroupOp> getNonPipelinedGroupFrom(Operation *op) {
99  auto it = operationToGroup.find(op);
100  if (it == operationToGroup.end())
101  return std::nullopt;
102 
103  if constexpr (std::is_same<TGroupOp, calyx::GroupInterface>::value)
104  return it->second;
105  else {
106  auto group = dyn_cast<TGroupOp>(it->second.getOperation());
107  assert(group && "Actual group type differed from expected group type");
108  return group;
109  }
110  }
111  /// Register reg as being the idx'th pipeline register for the stage.
112  void addPipelineReg(Operation *stage, calyx::RegisterOp reg, unsigned idx) {
113  assert(pipelineRegs[stage].count(idx) == 0);
114  assert(idx < stage->getNumResults());
115  pipelineRegs[stage][idx] = reg;
116  }
117 
118  /// Return a mapping of stage result indices to pipeline registers.
119  const DenseMap<unsigned, calyx::RegisterOp> &
120  getPipelineRegs(Operation *stage) {
121  return pipelineRegs[stage];
122  }
123 
124  /// Add a stage's groups to the pipeline prologue.
125  void addPipelinePrologue(Operation *op, SmallVector<StringAttr> groupNames) {
126  pipelinePrologue[op].push_back(groupNames);
127  }
128 
129  /// Add a stage's groups to the pipeline epilogue.
130  void addPipelineEpilogue(Operation *op, SmallVector<StringAttr> groupNames) {
131  pipelineEpilogue[op].push_back(groupNames);
132  }
133 
134  /// Get the pipeline prologue.
135  SmallVector<SmallVector<StringAttr>> getPipelinePrologue(Operation *op) {
136  return pipelinePrologue[op];
137  }
138 
139  /// Create the pipeline prologue.
140  void createPipelinePrologue(Operation *op, PatternRewriter &rewriter) {
141  auto stages = pipelinePrologue[op];
142  for (size_t i = 0, e = stages.size(); i < e; ++i) {
143  PatternRewriter::InsertionGuard g(rewriter);
144  auto parOp = rewriter.create<calyx::ParOp>(op->getLoc());
145  rewriter.setInsertionPointToStart(parOp.getBodyBlock());
146  for (size_t j = 0; j < i + 1; ++j)
147  for (auto group : stages[j])
148  rewriter.create<calyx::EnableOp>(op->getLoc(), group);
149  }
150  }
151 
152  /// Create the pipeline epilogue.
153  void createPipelineEpilogue(Operation *op, PatternRewriter &rewriter) {
154  auto stages = pipelineEpilogue[op];
155  for (size_t i = 0, e = stages.size(); i < e; ++i) {
156  PatternRewriter::InsertionGuard g(rewriter);
157  auto parOp = rewriter.create<calyx::ParOp>(op->getLoc());
158  rewriter.setInsertionPointToStart(parOp.getBodyBlock());
159  for (size_t j = i, f = stages.size(); j < f; ++j)
160  for (auto group : stages[j])
161  rewriter.create<calyx::EnableOp>(op->getLoc(), group);
162  }
163  }
164 
165 private:
166  /// A mapping between operations and the group to which it was assigned. This
167  /// is used for specific corner cases, such as pipeline stages that may not
168  /// actually pipeline any values.
169  DenseMap<Operation *, calyx::GroupInterface> operationToGroup;
170 
171  /// A mapping from pipeline stages to their registers.
172  DenseMap<Operation *, DenseMap<unsigned, calyx::RegisterOp>> pipelineRegs;
173 
174  /// A mapping from pipeline ops to a vector of vectors of group names that
175  /// constitute the pipeline prologue. Each inner vector consists of the groups
176  /// for one stage.
177  DenseMap<Operation *, SmallVector<SmallVector<StringAttr>>> pipelinePrologue;
178 
179  /// A mapping from pipeline ops to a vector of vectors of group names that
180  /// constitute the pipeline epilogue. Each inner vector consists of the groups
181  /// for one stage.
182  DenseMap<Operation *, SmallVector<SmallVector<StringAttr>>> pipelineEpilogue;
183 };
184 
185 /// Handles the current state of lowering of a Calyx component. It is mainly
186 /// used as a key/value store for recording information during partial lowering,
187 /// which is required at later lowering passes.
190  public calyx::LoopLoweringStateInterface<PipelineWhileOp>,
191  public PipelineScheduler {
192 public:
193  ComponentLoweringState(calyx::ComponentOp component)
194  : calyx::ComponentLoweringStateInterface(component) {}
195 };
196 
197 //===----------------------------------------------------------------------===//
198 // Conversion patterns
199 //===----------------------------------------------------------------------===//
200 
201 /// Iterate through the operations of a source function and instantiate
202 /// components or primitives based on the type of the operations.
204  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
205 
206  LogicalResult
208  PatternRewriter &rewriter) const override {
209  /// We walk the operations of the funcOp to ensure that all def's have
210  /// been visited before their uses.
211  bool opBuiltSuccessfully = true;
212  funcOp.walk([&](Operation *_op) {
213  opBuiltSuccessfully &=
214  TypeSwitch<mlir::Operation *, bool>(_op)
215  .template Case<arith::ConstantOp, ReturnOp, BranchOpInterface,
216  /// memref
217  memref::AllocOp, memref::AllocaOp, memref::LoadOp,
218  memref::StoreOp,
219  /// standard arithmetic
220  AddIOp, SubIOp, CmpIOp, ShLIOp, ShRUIOp, ShRSIOp,
221  AndIOp, XOrIOp, OrIOp, ExtUIOp, TruncIOp, MulIOp,
222  DivUIOp, RemUIOp, IndexCastOp,
223  /// static logic
224  LoopScheduleTerminatorOp>(
225  [&](auto op) { return buildOp(rewriter, op).succeeded(); })
226  .template Case<FuncOp, LoopSchedulePipelineOp,
227  LoopScheduleRegisterOp,
228  LoopSchedulePipelineStageOp>([&](auto) {
229  /// Skip: these special cases will be handled separately.
230  return true;
231  })
232  .Default([&](auto op) {
233  op->emitError() << "Unhandled operation during BuildOpGroups()";
234  return false;
235  });
236 
237  return opBuiltSuccessfully ? WalkResult::advance()
238  : WalkResult::interrupt();
239  });
240 
241  return success(opBuiltSuccessfully);
242  }
243 
244 private:
245  /// Op builder specializations.
246  LogicalResult buildOp(PatternRewriter &rewriter,
247  BranchOpInterface brOp) const;
248  LogicalResult buildOp(PatternRewriter &rewriter,
249  arith::ConstantOp constOp) const;
250  LogicalResult buildOp(PatternRewriter &rewriter, AddIOp op) const;
251  LogicalResult buildOp(PatternRewriter &rewriter, SubIOp op) const;
252  LogicalResult buildOp(PatternRewriter &rewriter, MulIOp op) const;
253  LogicalResult buildOp(PatternRewriter &rewriter, DivUIOp op) const;
254  LogicalResult buildOp(PatternRewriter &rewriter, RemUIOp op) const;
255  LogicalResult buildOp(PatternRewriter &rewriter, ShRUIOp op) const;
256  LogicalResult buildOp(PatternRewriter &rewriter, ShRSIOp op) const;
257  LogicalResult buildOp(PatternRewriter &rewriter, ShLIOp op) const;
258  LogicalResult buildOp(PatternRewriter &rewriter, AndIOp op) const;
259  LogicalResult buildOp(PatternRewriter &rewriter, OrIOp op) const;
260  LogicalResult buildOp(PatternRewriter &rewriter, XOrIOp op) const;
261  LogicalResult buildOp(PatternRewriter &rewriter, CmpIOp op) const;
262  LogicalResult buildOp(PatternRewriter &rewriter, TruncIOp op) const;
263  LogicalResult buildOp(PatternRewriter &rewriter, ExtUIOp op) const;
264  LogicalResult buildOp(PatternRewriter &rewriter, ReturnOp op) const;
265  LogicalResult buildOp(PatternRewriter &rewriter, IndexCastOp op) const;
266  LogicalResult buildOp(PatternRewriter &rewriter, memref::AllocOp op) const;
267  LogicalResult buildOp(PatternRewriter &rewriter, memref::AllocaOp op) const;
268  LogicalResult buildOp(PatternRewriter &rewriter, memref::LoadOp op) const;
269  LogicalResult buildOp(PatternRewriter &rewriter, memref::StoreOp op) const;
270  LogicalResult buildOp(PatternRewriter &rewriter,
271  LoopScheduleTerminatorOp op) 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  getState<ComponentLoweringState>().addBlockScheduleable(op->getBlock(),
352  group);
353 
354  rewriter.setInsertionPointToEnd(group.getBodyBlock());
355  rewriter.create<calyx::AssignOp>(loc, opPipe.getLeft(), op.getLhs());
356  rewriter.create<calyx::AssignOp>(loc, opPipe.getRight(), op.getRhs());
357  // Write the output to this register.
358  rewriter.create<calyx::AssignOp>(loc, reg.getIn(), out);
359  // The write enable port is high when the pipeline is done.
360  rewriter.create<calyx::AssignOp>(loc, reg.getWriteEn(), opPipe.getDone());
361  rewriter.create<calyx::AssignOp>(
362  loc, opPipe.getGo(),
363  createConstant(loc, rewriter, getComponent(), 1, 1));
364  // The group is done when the register write is complete.
365  rewriter.create<calyx::GroupDoneOp>(loc, reg.getDone());
366 
367  // Register the values for the pipeline.
368  getState<ComponentLoweringState>().registerEvaluatingGroup(out, group);
369  getState<ComponentLoweringState>().registerEvaluatingGroup(opPipe.getLeft(),
370  group);
371  getState<ComponentLoweringState>().registerEvaluatingGroup(
372  opPipe.getRight(), group);
373 
374  return success();
375  }
376 
377  /// Creates assignments within the provided group to the address ports of the
378  /// memoryOp based on the provided addressValues.
379  void assignAddressPorts(PatternRewriter &rewriter, Location loc,
380  calyx::GroupInterface group,
381  calyx::MemoryInterface memoryInterface,
382  Operation::operand_range addressValues) const {
383  IRRewriter::InsertionGuard guard(rewriter);
384  rewriter.setInsertionPointToEnd(group.getBody());
385  auto addrPorts = memoryInterface.addrPorts();
386  if (addressValues.empty()) {
387  assert(
388  addrPorts.size() == 1 &&
389  "We expected a 1 dimensional memory of size 1 because there were no "
390  "address assignment values");
391  // Assign 1'd0 to the address port.
392  rewriter.create<calyx::AssignOp>(
393  loc, addrPorts[0],
394  createConstant(loc, rewriter, getComponent(), 1, 0));
395  } else {
396  assert(addrPorts.size() == addressValues.size() &&
397  "Mismatch between number of address ports of the provided memory "
398  "and address assignment values");
399  for (auto address : enumerate(addressValues))
400  rewriter.create<calyx::AssignOp>(loc, addrPorts[address.index()],
401  address.value());
402  }
403  }
404 };
405 
406 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
407  memref::LoadOp loadOp) const {
408  Value memref = loadOp.getMemref();
409  auto memoryInterface =
410  getState<ComponentLoweringState>().getMemoryInterface(memref);
411  if (calyx::noStoresToMemory(memref) && calyx::singleLoadFromMemory(memref)) {
412  // Single load from memory; we do not need to write the
413  // output to a register. This is essentially a "combinational read" under
414  // current Calyx semantics with memory, and thus can be done in a
415  // combinational group. Note that if any stores are done to this memory,
416  // we require that the load and store be in separate non-combinational
417  // groups to avoid reading and writing to the same memory in the same group.
418  auto combGroup = createGroupForOp<calyx::CombGroupOp>(rewriter, loadOp);
419  assignAddressPorts(rewriter, loadOp.getLoc(), combGroup, memoryInterface,
420  loadOp.getIndices());
421 
422  // We refrain from replacing the loadOp result with
423  // memoryInterface.readData, since multiple loadOp's need to be converted
424  // to a single memory's ReadData. If this replacement is done now, we lose
425  // the link between which SSA memref::LoadOp values map to which groups for
426  // loading a value from the Calyx memory. At this point of lowering, we
427  // keep the memref::LoadOp SSA value, and do value replacement _after_
428  // control has been generated (see LateSSAReplacement). This is *vital* for
429  // things such as InlineCombGroups to be able to properly track which
430  // memory assignment groups belong to which accesses.
431  getState<ComponentLoweringState>().registerEvaluatingGroup(
432  loadOp.getResult(), combGroup);
433  } else {
434  auto group = createGroupForOp<calyx::GroupOp>(rewriter, loadOp);
435  assignAddressPorts(rewriter, loadOp.getLoc(), group, memoryInterface,
436  loadOp.getIndices());
437 
438  // Multiple loads from the same memory; In this case, we _may_ have a
439  // structural hazard in the design we generate. To get around this, we
440  // conservatively place a register in front of each load operation, and
441  // replace all uses of the loaded value with the register output. Proper
442  // handling of this requires the combinational group inliner/scheduler to
443  // be aware of when a combinational expression references multiple loaded
444  // values from the same memory, and then schedule assignments to temporary
445  // registers to get around the structural hazard.
446  auto reg = createRegister(
447  loadOp.getLoc(), rewriter, getComponent(),
448  loadOp.getMemRefType().getElementTypeBitWidth(),
449  getState<ComponentLoweringState>().getUniqueName("load"));
451  rewriter, group, getState<ComponentLoweringState>().getComponentOp(),
452  reg, memoryInterface.readData());
453  loadOp.getResult().replaceAllUsesWith(reg.getOut());
454  getState<ComponentLoweringState>().addBlockScheduleable(loadOp->getBlock(),
455  group);
456  }
457  return success();
458 }
459 
460 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
461  memref::StoreOp storeOp) const {
462  auto memoryInterface = getState<ComponentLoweringState>().getMemoryInterface(
463  storeOp.getMemref());
464  auto group = createGroupForOp<calyx::GroupOp>(rewriter, storeOp);
465 
466  // This is a sequential group, so register it as being scheduleable for the
467  // block.
468  getState<ComponentLoweringState>().addBlockScheduleable(storeOp->getBlock(),
469  group);
470  assignAddressPorts(rewriter, storeOp.getLoc(), group, memoryInterface,
471  storeOp.getIndices());
472  rewriter.setInsertionPointToEnd(group.getBodyBlock());
473  rewriter.create<calyx::AssignOp>(
474  storeOp.getLoc(), memoryInterface.writeData(), storeOp.getValueToStore());
475  rewriter.create<calyx::AssignOp>(
476  storeOp.getLoc(), memoryInterface.writeEn(),
477  createConstant(storeOp.getLoc(), rewriter, getComponent(), 1, 1));
478  if (memoryInterface.contentEnOpt().has_value()) {
479  // If memory has content enable, it must be asserted when writing
480  rewriter.create<calyx::AssignOp>(
481  storeOp.getLoc(), memoryInterface.contentEn(),
482  createConstant(storeOp.getLoc(), rewriter, getComponent(), 1, 1));
483  }
484  rewriter.create<calyx::GroupDoneOp>(storeOp.getLoc(), memoryInterface.done());
485 
486  getState<ComponentLoweringState>().registerNonPipelineOperations(storeOp,
487  group);
488 
489  return success();
490 }
491 
492 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
493  MulIOp mul) const {
494  Location loc = mul.getLoc();
495  Type width = mul.getResult().getType(), one = rewriter.getI1Type();
496  auto mulPipe =
497  getState<ComponentLoweringState>()
498  .getNewLibraryOpInstance<calyx::MultPipeLibOp>(
499  rewriter, loc, {one, one, one, width, width, width, one});
500  return buildLibraryBinaryPipeOp<calyx::MultPipeLibOp>(
501  rewriter, mul, mulPipe,
502  /*out=*/mulPipe.getOut());
503 }
504 
505 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
506  DivUIOp div) const {
507  Location loc = div.getLoc();
508  Type width = div.getResult().getType(), one = rewriter.getI1Type();
509  auto divPipe =
510  getState<ComponentLoweringState>()
511  .getNewLibraryOpInstance<calyx::DivUPipeLibOp>(
512  rewriter, loc, {one, one, one, width, width, width, width, one});
513  return buildLibraryBinaryPipeOp<calyx::DivUPipeLibOp>(
514  rewriter, div, divPipe,
515  /*out=*/divPipe.getOut());
516 }
517 
518 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
519  RemUIOp rem) const {
520  Location loc = rem.getLoc();
521  Type width = rem.getResult().getType(), one = rewriter.getI1Type();
522  auto remPipe =
523  getState<ComponentLoweringState>()
524  .getNewLibraryOpInstance<calyx::DivUPipeLibOp>(
525  rewriter, loc, {one, one, one, width, width, width, width, one});
526  return buildLibraryBinaryPipeOp<calyx::DivUPipeLibOp>(
527  rewriter, rem, remPipe,
528  /*out=*/remPipe.getOut());
529 }
530 
531 template <typename TAllocOp>
532 static LogicalResult buildAllocOp(ComponentLoweringState &componentState,
533  PatternRewriter &rewriter, TAllocOp allocOp) {
534  rewriter.setInsertionPointToStart(
535  componentState.getComponentOp().getBodyBlock());
536  MemRefType memtype = allocOp.getType();
537  SmallVector<int64_t> addrSizes;
538  SmallVector<int64_t> sizes;
539  for (int64_t dim : memtype.getShape()) {
540  sizes.push_back(dim);
541  addrSizes.push_back(calyx::handleZeroWidth(dim));
542  }
543  // If memref has no size (e.g., memref<i32>) create a 1 dimensional memory of
544  // size 1.
545  if (sizes.empty() && addrSizes.empty()) {
546  sizes.push_back(1);
547  addrSizes.push_back(1);
548  }
549  auto memoryOp = rewriter.create<calyx::MemoryOp>(
550  allocOp.getLoc(), componentState.getUniqueName("mem"),
551  memtype.getElementType().getIntOrFloatBitWidth(), sizes, addrSizes);
552  // Externalize memories by default. This makes it easier for the native
553  // compiler to provide initialized memories.
554  memoryOp->setAttr("external",
555  IntegerAttr::get(rewriter.getI1Type(), llvm::APInt(1, 1)));
556  componentState.registerMemoryInterface(allocOp.getResult(),
557  calyx::MemoryInterface(memoryOp));
558  return success();
559 }
560 
561 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
562  memref::AllocOp allocOp) const {
563  return buildAllocOp(getState<ComponentLoweringState>(), rewriter, allocOp);
564 }
565 
566 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
567  memref::AllocaOp allocOp) const {
568  return buildAllocOp(getState<ComponentLoweringState>(), rewriter, allocOp);
569 }
570 
571 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
572  LoopScheduleTerminatorOp term) const {
573  if (term.getOperands().size() == 0)
574  return success();
575 
576  // Replace the pipeline's result(s) with the terminator's results.
577  auto *pipeline = term->getParentOp();
578  for (size_t i = 0, e = pipeline->getNumResults(); i < e; ++i)
579  pipeline->getResult(i).replaceAllUsesWith(term.getResults()[i]);
580 
581  return success();
582 }
583 
584 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
585  BranchOpInterface brOp) const {
586  /// Branch argument passing group creation
587  /// Branch operands are passed through registers. In BuildBasicBlockRegs we
588  /// created registers for all branch arguments of each block. We now
589  /// create groups for assigning values to these registers.
590  Block *srcBlock = brOp->getBlock();
591  for (auto succBlock : enumerate(brOp->getSuccessors())) {
592  auto succOperands = brOp.getSuccessorOperands(succBlock.index());
593  if (succOperands.empty())
594  continue;
595  // Create operand passing group
596  std::string groupName = loweringState().blockName(srcBlock) + "_to_" +
597  loweringState().blockName(succBlock.value());
598  auto groupOp = calyx::createGroup<calyx::GroupOp>(rewriter, getComponent(),
599  brOp.getLoc(), groupName);
600  // Fetch block argument registers associated with the basic block
601  auto dstBlockArgRegs =
602  getState<ComponentLoweringState>().getBlockArgRegs(succBlock.value());
603  // Create register assignment for each block argument
604  for (auto arg : enumerate(succOperands.getForwardedOperands())) {
605  auto reg = dstBlockArgRegs[arg.index()];
607  rewriter, groupOp,
608  getState<ComponentLoweringState>().getComponentOp(), reg,
609  arg.value());
610  }
611  /// Register the group as a block argument group, to be executed
612  /// when entering the successor block from this block (srcBlock).
613  getState<ComponentLoweringState>().addBlockArgGroup(
614  srcBlock, succBlock.value(), groupOp);
615  }
616  return success();
617 }
618 
619 /// For each return statement, we create a new group for assigning to the
620 /// previously created return value registers.
621 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
622  ReturnOp retOp) const {
623  if (retOp.getNumOperands() == 0)
624  return success();
625 
626  std::string groupName =
627  getState<ComponentLoweringState>().getUniqueName("ret_assign");
628  auto groupOp = calyx::createGroup<calyx::GroupOp>(rewriter, getComponent(),
629  retOp.getLoc(), groupName);
630  for (auto op : enumerate(retOp.getOperands())) {
631  auto reg = getState<ComponentLoweringState>().getReturnReg(op.index());
633  rewriter, groupOp, getState<ComponentLoweringState>().getComponentOp(),
634  reg, op.value());
635  }
636  /// Schedule group for execution for when executing the return op block.
637  getState<ComponentLoweringState>().addBlockScheduleable(retOp->getBlock(),
638  groupOp);
639  return success();
640 }
641 
642 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
643  arith::ConstantOp constOp) const {
644  /// Move constant operations to the compOp body as hw::ConstantOp's.
645  APInt value;
646  calyx::matchConstantOp(constOp, value);
647  auto hwConstOp = rewriter.replaceOpWithNewOp<hw::ConstantOp>(constOp, value);
648  hwConstOp->moveAfter(getComponent().getBodyBlock(),
649  getComponent().getBodyBlock()->begin());
650  return success();
651 }
652 
653 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
654  AddIOp op) const {
655  return buildLibraryOp<calyx::CombGroupOp, calyx::AddLibOp>(rewriter, op);
656 }
657 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
658  SubIOp op) const {
659  return buildLibraryOp<calyx::CombGroupOp, calyx::SubLibOp>(rewriter, op);
660 }
661 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
662  ShRUIOp op) const {
663  return buildLibraryOp<calyx::CombGroupOp, calyx::RshLibOp>(rewriter, op);
664 }
665 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
666  ShRSIOp op) const {
667  return buildLibraryOp<calyx::CombGroupOp, calyx::SrshLibOp>(rewriter, op);
668 }
669 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
670  ShLIOp op) const {
671  return buildLibraryOp<calyx::CombGroupOp, calyx::LshLibOp>(rewriter, op);
672 }
673 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
674  AndIOp op) const {
675  return buildLibraryOp<calyx::CombGroupOp, calyx::AndLibOp>(rewriter, op);
676 }
677 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
678  OrIOp op) const {
679  return buildLibraryOp<calyx::CombGroupOp, calyx::OrLibOp>(rewriter, op);
680 }
681 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
682  XOrIOp op) const {
683  return buildLibraryOp<calyx::CombGroupOp, calyx::XorLibOp>(rewriter, op);
684 }
685 
686 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
687  CmpIOp op) const {
688  switch (op.getPredicate()) {
689  case CmpIPredicate::eq:
690  return buildLibraryOp<calyx::CombGroupOp, calyx::EqLibOp>(rewriter, op);
691  case CmpIPredicate::ne:
692  return buildLibraryOp<calyx::CombGroupOp, calyx::NeqLibOp>(rewriter, op);
693  case CmpIPredicate::uge:
694  return buildLibraryOp<calyx::CombGroupOp, calyx::GeLibOp>(rewriter, op);
695  case CmpIPredicate::ult:
696  return buildLibraryOp<calyx::CombGroupOp, calyx::LtLibOp>(rewriter, op);
697  case CmpIPredicate::ugt:
698  return buildLibraryOp<calyx::CombGroupOp, calyx::GtLibOp>(rewriter, op);
699  case CmpIPredicate::ule:
700  return buildLibraryOp<calyx::CombGroupOp, calyx::LeLibOp>(rewriter, op);
701  case CmpIPredicate::sge:
702  return buildLibraryOp<calyx::CombGroupOp, calyx::SgeLibOp>(rewriter, op);
703  case CmpIPredicate::slt:
704  return buildLibraryOp<calyx::CombGroupOp, calyx::SltLibOp>(rewriter, op);
705  case CmpIPredicate::sgt:
706  return buildLibraryOp<calyx::CombGroupOp, calyx::SgtLibOp>(rewriter, op);
707  case CmpIPredicate::sle:
708  return buildLibraryOp<calyx::CombGroupOp, calyx::SleLibOp>(rewriter, op);
709  }
710  llvm_unreachable("unsupported comparison predicate");
711 }
712 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
713  TruncIOp op) const {
714  return buildLibraryOp<calyx::CombGroupOp, calyx::SliceLibOp>(
715  rewriter, op, {op.getOperand().getType()}, {op.getType()});
716 }
717 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
718  ExtUIOp op) const {
719  return buildLibraryOp<calyx::CombGroupOp, calyx::PadLibOp>(
720  rewriter, op, {op.getOperand().getType()}, {op.getType()});
721 }
722 
723 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
724  IndexCastOp op) const {
725  Type sourceType = calyx::convIndexType(rewriter, op.getOperand().getType());
726  Type targetType = calyx::convIndexType(rewriter, op.getResult().getType());
727  unsigned targetBits = targetType.getIntOrFloatBitWidth();
728  unsigned sourceBits = sourceType.getIntOrFloatBitWidth();
729  LogicalResult res = success();
730 
731  if (targetBits == sourceBits) {
732  /// Drop the index cast and replace uses of the target value with the source
733  /// value.
734  op.getResult().replaceAllUsesWith(op.getOperand());
735  } else {
736  /// pad/slice the source operand.
737  if (sourceBits > targetBits)
738  res = buildLibraryOp<calyx::CombGroupOp, calyx::SliceLibOp>(
739  rewriter, op, {sourceType}, {targetType});
740  else
741  res = buildLibraryOp<calyx::CombGroupOp, calyx::PadLibOp>(
742  rewriter, op, {sourceType}, {targetType});
743  }
744  rewriter.eraseOp(op);
745  return res;
746 }
747 
748 /// Creates a new Calyx component for each FuncOp in the program.
750  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
751 
752  LogicalResult
754  PatternRewriter &rewriter) const override {
755  /// Maintain a mapping between funcOp input arguments and the port index
756  /// which the argument will eventually map to.
757  DenseMap<Value, unsigned> funcOpArgRewrites;
758 
759  /// Maintain a mapping between funcOp output indexes and the component
760  /// output port index which the return value will eventually map to.
761  DenseMap<unsigned, unsigned> funcOpResultMapping;
762 
763  /// Maintain a mapping between an external memory argument (identified by a
764  /// memref) and eventual component input- and output port indices that will
765  /// map to the memory ports. The pair denotes the start index of the memory
766  /// ports in the in- and output ports of the component. Ports are expected
767  /// to be ordered in the same manner as they are added by
768  /// calyx::appendPortsForExternalMemref.
769  DenseMap<Value, std::pair<unsigned, unsigned>> extMemoryCompPortIndices;
770 
771  /// Create I/O ports. Maintain separate in/out port vectors to determine
772  /// which port index each function argument will eventually map to.
773  SmallVector<calyx::PortInfo> inPorts, outPorts;
774  FunctionType funcType = funcOp.getFunctionType();
775  unsigned extMemCounter = 0;
776  for (auto arg : enumerate(funcOp.getArguments())) {
777  if (arg.value().getType().isa<MemRefType>()) {
778  /// External memories
779  auto memName =
780  "ext_mem" + std::to_string(extMemoryCompPortIndices.size());
781  extMemoryCompPortIndices[arg.value()] = {inPorts.size(),
782  outPorts.size()};
783  calyx::appendPortsForExternalMemref(rewriter, memName, arg.value(),
784  extMemCounter++, inPorts, outPorts);
785  } else {
786  /// Single-port arguments
787  auto inName = "in" + std::to_string(arg.index());
788  funcOpArgRewrites[arg.value()] = inPorts.size();
789  inPorts.push_back(calyx::PortInfo{
790  rewriter.getStringAttr(inName),
791  calyx::convIndexType(rewriter, arg.value().getType()),
793  DictionaryAttr::get(rewriter.getContext(), {})});
794  }
795  }
796  for (auto res : enumerate(funcType.getResults())) {
797  funcOpResultMapping[res.index()] = outPorts.size();
798  outPorts.push_back(calyx::PortInfo{
799  rewriter.getStringAttr("out" + std::to_string(res.index())),
800  calyx::convIndexType(rewriter, res.value()), calyx::Direction::Output,
801  DictionaryAttr::get(rewriter.getContext(), {})});
802  }
803 
804  /// We've now recorded all necessary indices. Merge in- and output ports
805  /// and add the required mandatory component ports.
806  auto ports = inPorts;
807  llvm::append_range(ports, outPorts);
808  calyx::addMandatoryComponentPorts(rewriter, ports);
809 
810  /// Create a calyx::ComponentOp corresponding to the to-be-lowered function.
811  auto compOp = rewriter.create<calyx::ComponentOp>(
812  funcOp.getLoc(), rewriter.getStringAttr(funcOp.getSymName()), ports);
813 
814  /// Mark this component as the toplevel.
815  compOp->setAttr("toplevel", rewriter.getUnitAttr());
816 
817  /// Store the function-to-component mapping.
818  functionMapping[funcOp] = compOp;
819  auto *compState = loweringState().getState<ComponentLoweringState>(compOp);
820  compState->setFuncOpResultMapping(funcOpResultMapping);
821 
822  /// Rewrite funcOp SSA argument values to the CompOp arguments.
823  for (auto &mapping : funcOpArgRewrites)
824  mapping.getFirst().replaceAllUsesWith(
825  compOp.getArgument(mapping.getSecond()));
826 
827  /// Register external memories
828  for (auto extMemPortIndices : extMemoryCompPortIndices) {
829  /// Create a mapping for the in- and output ports using the Calyx memory
830  /// port structure.
831  calyx::MemoryPortsImpl extMemPorts;
832  unsigned inPortsIt = extMemPortIndices.getSecond().first;
833  unsigned outPortsIt = extMemPortIndices.getSecond().second +
834  compOp.getInputPortInfo().size();
835  extMemPorts.readData = compOp.getArgument(inPortsIt++);
836  extMemPorts.done = compOp.getArgument(inPortsIt);
837  extMemPorts.writeData = compOp.getArgument(outPortsIt++);
838  unsigned nAddresses = extMemPortIndices.getFirst()
839  .getType()
840  .cast<MemRefType>()
841  .getShape()
842  .size();
843  for (unsigned j = 0; j < nAddresses; ++j)
844  extMemPorts.addrPorts.push_back(compOp.getArgument(outPortsIt++));
845  extMemPorts.writeEn = compOp.getArgument(outPortsIt);
846 
847  /// Register the external memory ports as a memory interface within the
848  /// component.
849  compState->registerMemoryInterface(extMemPortIndices.getFirst(),
850  calyx::MemoryInterface(extMemPorts));
851  }
852 
853  return success();
854  }
855 };
856 
857 /// In BuildWhileGroups, a register is created for each iteration argumenet of
858 /// the while op. These registers are then written to on the while op
859 /// terminating yield operation alongside before executing the whileOp in the
860 /// schedule, to set the initial values of the argument registers.
862  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
863 
864  LogicalResult
866  PatternRewriter &rewriter) const override {
867  LogicalResult res = success();
868  funcOp.walk([&](Operation *op) {
869  if (!isa<LoopSchedulePipelineOp>(op))
870  return WalkResult::advance();
871 
872  PipelineWhileOp whileOp(cast<LoopSchedulePipelineOp>(op));
873 
874  getState<ComponentLoweringState>().setUniqueName(whileOp.getOperation(),
875  "while");
876 
877  /// Create iteration argument registers.
878  /// The iteration argument registers will be referenced:
879  /// - In the "before" part of the while loop, calculating the conditional,
880  /// - In the "after" part of the while loop,
881  /// - Outside the while loop, rewriting the while loop return values.
882  for (auto arg : enumerate(whileOp.getBodyArgs())) {
883  std::string name = getState<ComponentLoweringState>()
884  .getUniqueName(whileOp.getOperation())
885  .str() +
886  "_arg" + std::to_string(arg.index());
887  auto reg =
888  createRegister(arg.value().getLoc(), rewriter, getComponent(),
889  arg.value().getType().getIntOrFloatBitWidth(), name);
890  getState<ComponentLoweringState>().addLoopIterReg(whileOp, reg,
891  arg.index());
892  arg.value().replaceAllUsesWith(reg.getOut());
893 
894  /// Also replace uses in the "before" region of the while loop
895  whileOp.getConditionBlock()
896  ->getArgument(arg.index())
897  .replaceAllUsesWith(reg.getOut());
898  }
899 
900  /// Create iter args initial value assignment group(s), one per register.
901  SmallVector<calyx::GroupOp> initGroups;
902  auto numOperands = whileOp.getOperation()->getNumOperands();
903  for (size_t i = 0; i < numOperands; ++i) {
904  auto initGroupOp =
905  getState<ComponentLoweringState>().buildLoopIterArgAssignments(
906  rewriter, whileOp,
907  getState<ComponentLoweringState>().getComponentOp(),
908  getState<ComponentLoweringState>().getUniqueName(
909  whileOp.getOperation()) +
910  "_init_" + std::to_string(i),
911  whileOp.getOperation()->getOpOperand(i));
912  initGroups.push_back(initGroupOp);
913  }
914 
915  /// Add the while op to the list of scheduleable things in the current
916  /// block.
917  getState<ComponentLoweringState>().addBlockScheduleable(
918  whileOp.getOperation()->getBlock(), PipelineScheduleable{
919  whileOp,
920  initGroups,
921  });
922  return WalkResult::advance();
923  });
924  return res;
925  }
926 };
927 
928 /// Builds registers for each pipeline stage in the program.
930  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
931 
932  LogicalResult
934  PatternRewriter &rewriter) const override {
935  funcOp.walk([&](LoopScheduleRegisterOp op) {
936  // Condition registers are handled in BuildWhileGroups.
937  auto *parent = op->getParentOp();
938  auto stage = dyn_cast<LoopSchedulePipelineStageOp>(parent);
939  if (!stage)
940  return;
941 
942  // Create a register for each stage.
943  for (auto &operand : op->getOpOperands()) {
944  unsigned i = operand.getOperandNumber();
945  // Iter args are created in BuildWhileGroups, so just mark the iter arg
946  // register as the appropriate pipeline register.
947  Value stageResult = stage.getResult(i);
948  bool isIterArg = false;
949  for (auto &use : stageResult.getUses()) {
950  if (auto term = dyn_cast<LoopScheduleTerminatorOp>(use.getOwner())) {
951  if (use.getOperandNumber() < term.getIterArgs().size()) {
952  PipelineWhileOp whileOp(
953  dyn_cast<LoopSchedulePipelineOp>(stage->getParentOp()));
954  auto reg = getState<ComponentLoweringState>().getLoopIterReg(
955  whileOp, use.getOperandNumber());
956  getState<ComponentLoweringState>().addPipelineReg(stage, reg, i);
957  isIterArg = true;
958  }
959  }
960  }
961  if (isIterArg)
962  continue;
963 
964  // Create a register for passing this result to later stages.
965  Value value = operand.get();
966  Type resultType = value.getType();
967  assert(resultType.isa<IntegerType>() &&
968  "unsupported pipeline result type");
969  auto name = SmallString<20>("stage_");
970  name += std::to_string(stage.getStageNumber());
971  name += "_register_";
972  name += std::to_string(i);
973  unsigned width = resultType.getIntOrFloatBitWidth();
974  auto reg = createRegister(value.getLoc(), rewriter, getComponent(),
975  width, name);
976  getState<ComponentLoweringState>().addPipelineReg(stage, reg, i);
977 
978  // Note that we do not use replace all uses with here as in
979  // BuildBasicBlockRegs. Instead, we wait until after BuildOpGroups, and
980  // replace all uses inside BuildPipelineGroups, once the pipeline
981  // register created here has been assigned to.
982  }
983  });
984  return success();
985  }
986 };
987 
988 /// Builds groups for assigning registers for pipeline stages.
990  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
991 
992  LogicalResult
994  PatternRewriter &rewriter) const override {
995  for (auto pipeline : funcOp.getOps<LoopSchedulePipelineOp>())
996  for (auto stage :
997  pipeline.getStagesBlock().getOps<LoopSchedulePipelineStageOp>())
998  if (failed(buildStageGroups(pipeline, stage, rewriter)))
999  return failure();
1000 
1001  return success();
1002  }
1003 
1004  LogicalResult buildStageGroups(LoopSchedulePipelineOp whileOp,
1005  LoopSchedulePipelineStageOp stage,
1006  PatternRewriter &rewriter) const {
1007  // Collect pipeline registers for stage.
1008  auto pipelineRegisters =
1009  getState<ComponentLoweringState>().getPipelineRegs(stage);
1010  // Get the number of pipeline stages in the stages block, excluding the
1011  // terminator. The verifier guarantees there is at least one stage followed
1012  // by a terminator.
1013  size_t numStages = whileOp.getStagesBlock().getOperations().size() - 1;
1014  assert(numStages > 0);
1015 
1016  // Collect group names for the prologue or epilogue.
1017  SmallVector<StringAttr> prologueGroups, epilogueGroups;
1018 
1019  auto updatePrologueAndEpilogue = [&](calyx::GroupOp group) {
1020  // Mark the group for scheduling in the pipeline's block.
1021  getState<ComponentLoweringState>().addBlockScheduleable(stage->getBlock(),
1022  group);
1023 
1024  // Add the group to the prologue or epilogue for this stage as
1025  // necessary. The goal is to fill the pipeline so it will be in steady
1026  // state after the prologue, and drain the pipeline from steady state in
1027  // the epilogue. Every stage but the last should have its groups in the
1028  // prologue, and every stage but the first should have its groups in the
1029  // epilogue.
1030  unsigned stageNumber = stage.getStageNumber();
1031  if (stageNumber < numStages - 1)
1032  prologueGroups.push_back(group.getSymNameAttr());
1033  if (stageNumber > 0)
1034  epilogueGroups.push_back(group.getSymNameAttr());
1035  };
1036 
1037  MutableArrayRef<OpOperand> operands =
1038  stage.getBodyBlock().getTerminator()->getOpOperands();
1039  bool isStageWithNoPipelinedValues =
1040  operands.empty() && !stage.getBodyBlock().empty();
1041  if (isStageWithNoPipelinedValues) {
1042  // Covers the case where there are no values that need to be passed
1043  // through to the next stage, e.g., some intermediary store.
1044  for (auto &op : stage.getBodyBlock())
1045  if (auto group = getState<ComponentLoweringState>()
1046  .getNonPipelinedGroupFrom<calyx::GroupOp>(&op))
1047  updatePrologueAndEpilogue(*group);
1048  }
1049 
1050  for (auto &operand : operands) {
1051  unsigned i = operand.getOperandNumber();
1052  Value value = operand.get();
1053 
1054  // Get the pipeline register for that result.
1055  auto pipelineRegister = pipelineRegisters[i];
1056 
1057  // Get the evaluating group for that value.
1058  calyx::GroupInterface evaluatingGroup =
1059  getState<ComponentLoweringState>().getEvaluatingGroup(value);
1060 
1061  // Remember the final group for this stage result.
1062  calyx::GroupOp group;
1063 
1064  // Stitch the register in, depending on whether the group was
1065  // combinational or sequential.
1066  if (auto combGroup =
1067  dyn_cast<calyx::CombGroupOp>(evaluatingGroup.getOperation()))
1068  group =
1069  convertCombToSeqGroup(combGroup, pipelineRegister, value, rewriter);
1070  else
1071  group =
1072  replaceGroupRegister(evaluatingGroup, pipelineRegister, rewriter);
1073 
1074  // Replace the stage result uses with the register out.
1075  stage.getResult(i).replaceAllUsesWith(pipelineRegister.getOut());
1076 
1077  updatePrologueAndEpilogue(group);
1078  }
1079 
1080  // Append the stage to the prologue or epilogue list of stages if any groups
1081  // were added for this stage. We append a list of groups for each stage, so
1082  // we can group by stage later, when we generate the schedule.
1083  if (!prologueGroups.empty())
1084  getState<ComponentLoweringState>().addPipelinePrologue(whileOp,
1085  prologueGroups);
1086  if (!epilogueGroups.empty())
1087  getState<ComponentLoweringState>().addPipelineEpilogue(whileOp,
1088  epilogueGroups);
1089 
1090  return success();
1091  }
1092 
1093  calyx::GroupOp convertCombToSeqGroup(calyx::CombGroupOp combGroup,
1094  calyx::RegisterOp pipelineRegister,
1095  Value value,
1096  PatternRewriter &rewriter) const {
1097  // Create a sequential group and replace the comb group.
1098  PatternRewriter::InsertionGuard g(rewriter);
1099  rewriter.setInsertionPoint(combGroup);
1100  auto group = rewriter.create<calyx::GroupOp>(combGroup.getLoc(),
1101  combGroup.getName());
1102  rewriter.cloneRegionBefore(combGroup.getBodyRegion(),
1103  &group.getBody().front());
1104  group.getBodyRegion().back().erase();
1105  rewriter.eraseOp(combGroup);
1106 
1107  // Stitch evaluating group to register.
1109  rewriter, group, getState<ComponentLoweringState>().getComponentOp(),
1110  pipelineRegister, value);
1111 
1112  // Mark the new group as the evaluating group.
1113  for (auto assign : group.getOps<calyx::AssignOp>())
1114  getState<ComponentLoweringState>().registerEvaluatingGroup(
1115  assign.getSrc(), group);
1116 
1117  return group;
1118  }
1119 
1120  calyx::GroupOp replaceGroupRegister(calyx::GroupInterface evaluatingGroup,
1121  calyx::RegisterOp pipelineRegister,
1122  PatternRewriter &rewriter) const {
1123  auto group = cast<calyx::GroupOp>(evaluatingGroup.getOperation());
1124 
1125  // Get the group and register that is temporarily being written to.
1126  auto doneOp = group.getDoneOp();
1127  auto tempReg =
1128  cast<calyx::RegisterOp>(doneOp.getSrc().cast<OpResult>().getOwner());
1129  auto tempIn = tempReg.getIn();
1130  auto tempWriteEn = tempReg.getWriteEn();
1131 
1132  // Replace the register write with a write to the pipeline register.
1133  for (auto assign : group.getOps<calyx::AssignOp>()) {
1134  if (assign.getDest() == tempIn)
1135  assign.getDestMutable().assign(pipelineRegister.getIn());
1136  else if (assign.getDest() == tempWriteEn)
1137  assign.getDestMutable().assign(pipelineRegister.getWriteEn());
1138  }
1139  doneOp.getSrcMutable().assign(pipelineRegister.getDone());
1140 
1141  // Remove the old register completely.
1142  rewriter.eraseOp(tempReg);
1143 
1144  return group;
1145  }
1146 };
1147 
1148 /// Builds a control schedule by traversing the CFG of the function and
1149 /// associating this with the previously created groups.
1150 /// For simplicity, the generated control flow is expanded for all possible
1151 /// paths in the input DAG. This elaborated control flow is later reduced in
1152 /// the runControlFlowSimplification passes.
1154  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1155 
1156  LogicalResult
1158  PatternRewriter &rewriter) const override {
1159  auto *entryBlock = &funcOp.getBlocks().front();
1160  rewriter.setInsertionPointToStart(
1161  getComponent().getControlOp().getBodyBlock());
1162  auto topLevelSeqOp = rewriter.create<calyx::SeqOp>(funcOp.getLoc());
1163  DenseSet<Block *> path;
1164  return buildCFGControl(path, rewriter, topLevelSeqOp.getBodyBlock(),
1165  nullptr, entryBlock);
1166  }
1167 
1168 private:
1169  /// Sequentially schedules the groups that registered themselves with
1170  /// 'block'.
1171  LogicalResult scheduleBasicBlock(PatternRewriter &rewriter,
1172  const DenseSet<Block *> &path,
1173  mlir::Block *parentCtrlBlock,
1174  mlir::Block *block) const {
1175  auto compBlockScheduleables =
1176  getState<ComponentLoweringState>().getBlockScheduleables(block);
1177  auto loc = block->front().getLoc();
1178 
1179  if (compBlockScheduleables.size() > 1) {
1180  auto seqOp = rewriter.create<calyx::SeqOp>(loc);
1181  parentCtrlBlock = seqOp.getBodyBlock();
1182  }
1183 
1184  for (auto &group : compBlockScheduleables) {
1185  rewriter.setInsertionPointToEnd(parentCtrlBlock);
1186  if (auto groupPtr = std::get_if<calyx::GroupOp>(&group); groupPtr) {
1187  rewriter.create<calyx::EnableOp>(groupPtr->getLoc(),
1188  groupPtr->getSymName());
1189  } else if (auto *pipeSchedPtr = std::get_if<PipelineScheduleable>(&group);
1190  pipeSchedPtr) {
1191  auto &whileOp = pipeSchedPtr->whileOp;
1192 
1193  auto whileCtrlOp =
1194  buildWhileCtrlOp(whileOp, pipeSchedPtr->initGroups, rewriter);
1195  rewriter.setInsertionPointToEnd(whileCtrlOp.getBodyBlock());
1196  auto whileBodyOp =
1197  rewriter.create<calyx::ParOp>(whileOp.getOperation()->getLoc());
1198  rewriter.setInsertionPointToEnd(whileBodyOp.getBodyBlock());
1199 
1200  /// Schedule pipeline stages in the parallel group directly.
1201  auto bodyBlockScheduleables =
1202  getState<ComponentLoweringState>().getBlockScheduleables(
1203  whileOp.getBodyBlock());
1204  for (auto &group : bodyBlockScheduleables)
1205  if (auto *groupPtr = std::get_if<calyx::GroupOp>(&group); groupPtr)
1206  rewriter.create<calyx::EnableOp>(groupPtr->getLoc(),
1207  groupPtr->getSymName());
1208  else
1209  return whileOp.getOperation()->emitError(
1210  "Unsupported block schedulable");
1211 
1212  // Add any prologue or epilogue.
1213  PatternRewriter::InsertionGuard g(rewriter);
1214  rewriter.setInsertionPoint(whileCtrlOp);
1215  getState<ComponentLoweringState>().createPipelinePrologue(
1216  whileOp.getOperation(), rewriter);
1217  rewriter.setInsertionPointAfter(whileCtrlOp);
1218  getState<ComponentLoweringState>().createPipelineEpilogue(
1219  whileOp.getOperation(), rewriter);
1220  } else
1221  llvm_unreachable("Unknown scheduleable");
1222  }
1223  return success();
1224  }
1225 
1226  /// Schedules a block by inserting a branch argument assignment block (if any)
1227  /// before recursing into the scheduling of the block innards.
1228  /// Blocks 'from' and 'to' refer to blocks in the source program.
1229  /// parentCtrlBlock refers to the control block wherein control operations are
1230  /// to be inserted.
1231  LogicalResult schedulePath(PatternRewriter &rewriter,
1232  const DenseSet<Block *> &path, Location loc,
1233  Block *from, Block *to,
1234  Block *parentCtrlBlock) const {
1235  /// Schedule any registered block arguments to be executed before the body
1236  /// of the branch.
1237  rewriter.setInsertionPointToEnd(parentCtrlBlock);
1238  auto preSeqOp = rewriter.create<calyx::SeqOp>(loc);
1239  rewriter.setInsertionPointToEnd(preSeqOp.getBodyBlock());
1240  for (auto barg :
1241  getState<ComponentLoweringState>().getBlockArgGroups(from, to))
1242  rewriter.create<calyx::EnableOp>(barg.getLoc(), barg.getSymName());
1243 
1244  return buildCFGControl(path, rewriter, parentCtrlBlock, from, to);
1245  }
1246 
1247  LogicalResult buildCFGControl(DenseSet<Block *> path,
1248  PatternRewriter &rewriter,
1249  mlir::Block *parentCtrlBlock,
1250  mlir::Block *preBlock,
1251  mlir::Block *block) const {
1252  if (path.count(block) != 0)
1253  return preBlock->getTerminator()->emitError()
1254  << "CFG backedge detected. Loops must be raised to 'scf.while' or "
1255  "'scf.for' operations.";
1256 
1257  rewriter.setInsertionPointToEnd(parentCtrlBlock);
1258  LogicalResult bbSchedResult =
1259  scheduleBasicBlock(rewriter, path, parentCtrlBlock, block);
1260  if (bbSchedResult.failed())
1261  return bbSchedResult;
1262 
1263  path.insert(block);
1264  auto successors = block->getSuccessors();
1265  auto nSuccessors = successors.size();
1266  if (nSuccessors > 0) {
1267  auto brOp = dyn_cast<BranchOpInterface>(block->getTerminator());
1268  assert(brOp);
1269  if (nSuccessors > 1) {
1270  /// TODO(mortbopet): we could choose to support ie. std.switch, but it
1271  /// would probably be easier to just require it to be lowered
1272  /// beforehand.
1273  assert(nSuccessors == 2 &&
1274  "only conditional branches supported for now...");
1275  /// Wrap each branch inside an if/else.
1276  auto cond = brOp->getOperand(0);
1277  auto condGroup = getState<ComponentLoweringState>()
1278  .getEvaluatingGroup<calyx::CombGroupOp>(cond);
1279  auto symbolAttr = FlatSymbolRefAttr::get(
1280  StringAttr::get(getContext(), condGroup.getSymName()));
1281 
1282  auto ifOp = rewriter.create<calyx::IfOp>(
1283  brOp->getLoc(), cond, symbolAttr, /*initializeElseBody=*/true);
1284  rewriter.setInsertionPointToStart(ifOp.getThenBody());
1285  auto thenSeqOp = rewriter.create<calyx::SeqOp>(brOp.getLoc());
1286  rewriter.setInsertionPointToStart(ifOp.getElseBody());
1287  auto elseSeqOp = rewriter.create<calyx::SeqOp>(brOp.getLoc());
1288 
1289  bool trueBrSchedSuccess =
1290  schedulePath(rewriter, path, brOp.getLoc(), block, successors[0],
1291  thenSeqOp.getBodyBlock())
1292  .succeeded();
1293  bool falseBrSchedSuccess = true;
1294  if (trueBrSchedSuccess) {
1295  falseBrSchedSuccess =
1296  schedulePath(rewriter, path, brOp.getLoc(), block, successors[1],
1297  elseSeqOp.getBodyBlock())
1298  .succeeded();
1299  }
1300 
1301  return success(trueBrSchedSuccess && falseBrSchedSuccess);
1302  } else {
1303  /// Schedule sequentially within the current parent control block.
1304  return schedulePath(rewriter, path, brOp.getLoc(), block,
1305  successors.front(), parentCtrlBlock);
1306  }
1307  }
1308  return success();
1309  }
1310 
1311  calyx::WhileOp buildWhileCtrlOp(PipelineWhileOp whileOp,
1312  SmallVector<calyx::GroupOp> initGroups,
1313  PatternRewriter &rewriter) const {
1314  Location loc = whileOp.getLoc();
1315  /// Insert while iter arg initialization group(s). Emit a
1316  /// parallel group to assign one or more registers all at once.
1317  {
1318  PatternRewriter::InsertionGuard g(rewriter);
1319  auto parOp = rewriter.create<calyx::ParOp>(loc);
1320  rewriter.setInsertionPointToStart(parOp.getBodyBlock());
1321  for (calyx::GroupOp group : initGroups)
1322  rewriter.create<calyx::EnableOp>(group.getLoc(), group.getName());
1323  }
1324 
1325  /// Insert the while op itself.
1326  auto cond = whileOp.getConditionValue();
1327  auto condGroup = getState<ComponentLoweringState>()
1328  .getEvaluatingGroup<calyx::CombGroupOp>(cond);
1329  auto symbolAttr = FlatSymbolRefAttr::get(
1330  StringAttr::get(getContext(), condGroup.getSymName()));
1331  auto whileCtrlOp = rewriter.create<calyx::WhileOp>(loc, cond, symbolAttr);
1332 
1333  /// If a bound was specified, add it.
1334  if (auto bound = whileOp.getBound()) {
1335  // Subtract the number of iterations unrolled into the prologue.
1336  auto prologue = getState<ComponentLoweringState>().getPipelinePrologue(
1337  whileOp.getOperation());
1338  auto unrolledBound = *bound - prologue.size();
1339  whileCtrlOp->setAttr("bound", rewriter.getI64IntegerAttr(unrolledBound));
1340  }
1341 
1342  return whileCtrlOp;
1343  }
1344 };
1345 
1346 /// LateSSAReplacement contains various functions for replacing SSA values that
1347 /// were not replaced during op construction.
1349  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1350 
1351  LogicalResult partiallyLowerFuncToComp(FuncOp funcOp,
1352  PatternRewriter &) const override {
1353  funcOp.walk([&](memref::LoadOp loadOp) {
1354  if (calyx::singleLoadFromMemory(loadOp)) {
1355  /// In buildOpGroups we did not replace loadOp's results, to ensure a
1356  /// link between evaluating groups (which fix the input addresses of a
1357  /// memory op) and a readData result. Now, we may replace these SSA
1358  /// values with their memoryOp readData output.
1359  loadOp.getResult().replaceAllUsesWith(
1360  getState<ComponentLoweringState>()
1361  .getMemoryInterface(loadOp.getMemref())
1362  .readData());
1363  }
1364  });
1365 
1366  return success();
1367  }
1368 };
1369 
1370 /// Erases FuncOp operations.
1372  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1373 
1374  LogicalResult matchAndRewrite(FuncOp funcOp,
1375  PatternRewriter &rewriter) const override {
1376  rewriter.eraseOp(funcOp);
1377  return success();
1378  }
1379 
1380  LogicalResult
1382  PatternRewriter &rewriter) const override {
1383  return success();
1384  }
1385 };
1386 
1387 //===----------------------------------------------------------------------===//
1388 // Pass driver
1389 //===----------------------------------------------------------------------===//
1391  : public LoopScheduleToCalyxBase<LoopScheduleToCalyxPass> {
1392 public:
1395  partialPatternRes(success()) {}
1396  void runOnOperation() override;
1397 
1398  LogicalResult setTopLevelFunction(mlir::ModuleOp moduleOp,
1399  std::string &topLevelFunction) {
1400  if (!topLevelFunctionOpt.empty()) {
1401  if (SymbolTable::lookupSymbolIn(moduleOp, topLevelFunctionOpt) ==
1402  nullptr) {
1403  moduleOp.emitError() << "Top level function '" << topLevelFunctionOpt
1404  << "' not found in module.";
1405  return failure();
1406  }
1407  topLevelFunction = topLevelFunctionOpt;
1408  } else {
1409  /// No top level function set; infer top level if the module only contains
1410  /// a single function, else, throw error.
1411  auto funcOps = moduleOp.getOps<FuncOp>();
1412  if (std::distance(funcOps.begin(), funcOps.end()) == 1)
1413  topLevelFunction = (*funcOps.begin()).getSymName().str();
1414  else {
1415  moduleOp.emitError()
1416  << "Module contains multiple functions, but no top level "
1417  "function was set. Please see --top-level-function";
1418  return failure();
1419  }
1420  }
1421  return success();
1422  }
1423 
1425  enum class Strategy { Once, Greedy };
1426  RewritePatternSet pattern;
1428  };
1429 
1430  //// Labels the entry point of a Calyx program.
1431  /// Furthermore, this function performs validation on the input function,
1432  /// to ensure that we've implemented the capabilities necessary to convert
1433  /// it.
1434  LogicalResult labelEntryPoint(StringRef topLevelFunction) {
1435  // Program legalization - the partial conversion driver will not run
1436  // unless some pattern is provided - provide a dummy pattern.
1437  struct DummyPattern : public OpRewritePattern<mlir::ModuleOp> {
1438  using OpRewritePattern::OpRewritePattern;
1439  LogicalResult matchAndRewrite(mlir::ModuleOp,
1440  PatternRewriter &) const override {
1441  return failure();
1442  }
1443  };
1444 
1445  ConversionTarget target(getContext());
1446  target.addLegalDialect<calyx::CalyxDialect>();
1447  target.addLegalDialect<scf::SCFDialect>();
1448  target.addIllegalDialect<hw::HWDialect>();
1449  target.addIllegalDialect<comb::CombDialect>();
1450 
1451  // For loops should have been lowered to while loops
1452  target.addIllegalOp<scf::ForOp>();
1453 
1454  // Only accept std operations which we've added lowerings for
1455  target.addIllegalDialect<FuncDialect>();
1456  target.addIllegalDialect<ArithDialect>();
1457  target.addLegalOp<AddIOp, SubIOp, CmpIOp, ShLIOp, ShRUIOp, ShRSIOp, AndIOp,
1458  XOrIOp, OrIOp, ExtUIOp, TruncIOp, CondBranchOp, BranchOp,
1459  MulIOp, DivUIOp, DivSIOp, RemUIOp, RemSIOp, ReturnOp,
1460  arith::ConstantOp, IndexCastOp, FuncOp, ExtSIOp>();
1461 
1462  RewritePatternSet legalizePatterns(&getContext());
1463  legalizePatterns.add<DummyPattern>(&getContext());
1464  DenseSet<Operation *> legalizedOps;
1465  if (applyPartialConversion(getOperation(), target,
1466  std::move(legalizePatterns))
1467  .failed())
1468  return failure();
1469 
1470  // Program conversion
1471  return calyx::applyModuleOpConversion(getOperation(), topLevelFunction);
1472  }
1473 
1474  /// 'Once' patterns are expected to take an additional LogicalResult&
1475  /// argument, to forward their result state (greedyPatternRewriteDriver
1476  /// results are skipped for Once patterns).
1477  template <typename TPattern, typename... PatternArgs>
1478  void addOncePattern(SmallVectorImpl<LoweringPattern> &patterns,
1479  PatternArgs &&...args) {
1480  RewritePatternSet ps(&getContext());
1481  ps.add<TPattern>(&getContext(), partialPatternRes, args...);
1482  patterns.push_back(
1483  LoweringPattern{std::move(ps), LoweringPattern::Strategy::Once});
1484  }
1485 
1486  template <typename TPattern, typename... PatternArgs>
1487  void addGreedyPattern(SmallVectorImpl<LoweringPattern> &patterns,
1488  PatternArgs &&...args) {
1489  RewritePatternSet ps(&getContext());
1490  ps.add<TPattern>(&getContext(), args...);
1491  patterns.push_back(
1492  LoweringPattern{std::move(ps), LoweringPattern::Strategy::Greedy});
1493  }
1494 
1495  LogicalResult runPartialPattern(RewritePatternSet &pattern, bool runOnce) {
1496  assert(pattern.getNativePatterns().size() == 1 &&
1497  "Should only apply 1 partial lowering pattern at once");
1498 
1499  // During component creation, the function body is inlined into the
1500  // component body for further processing. However, proper control flow
1501  // will only be established later in the conversion process, so ensure
1502  // that rewriter optimizations (especially DCE) are disabled.
1503  GreedyRewriteConfig config;
1504  config.enableRegionSimplification = false;
1505  if (runOnce)
1506  config.maxIterations = 1;
1507 
1508  /// Can't return applyPatternsAndFoldGreedily. Root isn't
1509  /// necessarily erased so it will always return failed(). Instead,
1510  /// forward the 'succeeded' value from PartialLoweringPatternBase.
1511  (void)applyPatternsAndFoldGreedily(getOperation(), std::move(pattern),
1512  config);
1513  return partialPatternRes;
1514  }
1515 
1516 private:
1517  LogicalResult partialPatternRes;
1518  std::shared_ptr<calyx::CalyxLoweringState> loweringState = nullptr;
1519 };
1520 
1521 void LoopScheduleToCalyxPass::runOnOperation() {
1522  // Clear internal state. See https://github.com/llvm/circt/issues/3235
1523  loweringState.reset();
1524  partialPatternRes = LogicalResult::failure();
1525 
1526  std::string topLevelFunction;
1527  if (failed(setTopLevelFunction(getOperation(), topLevelFunction))) {
1528  signalPassFailure();
1529  return;
1530  }
1531 
1532  /// Start conversion
1533  if (failed(labelEntryPoint(topLevelFunction))) {
1534  signalPassFailure();
1535  return;
1536  }
1537  loweringState = std::make_shared<calyx::CalyxLoweringState>(getOperation(),
1538  topLevelFunction);
1539 
1540  /// --------------------------------------------------------------------------
1541  /// If you are a developer, it may be helpful to add a
1542  /// 'getOperation()->dump()' call after the execution of each stage to
1543  /// view the transformations that's going on.
1544  /// --------------------------------------------------------------------------
1545 
1546  /// A mapping is maintained between a function operation and its corresponding
1547  /// Calyx component.
1548  DenseMap<FuncOp, calyx::ComponentOp> funcMap;
1549  SmallVector<LoweringPattern, 8> loweringPatterns;
1550  calyx::PatternApplicationState patternState;
1551 
1552  /// Creates a new Calyx component for each FuncOp in the inpurt module.
1553  addOncePattern<FuncOpConversion>(loweringPatterns, patternState, funcMap,
1554  *loweringState);
1555 
1556  /// This pattern converts all index typed values to an i32 integer.
1557  addOncePattern<calyx::ConvertIndexTypes>(loweringPatterns, patternState,
1558  funcMap, *loweringState);
1559 
1560  /// This pattern creates registers for all basic-block arguments.
1561  addOncePattern<calyx::BuildBasicBlockRegs>(loweringPatterns, patternState,
1562  funcMap, *loweringState);
1563 
1564  /// This pattern creates registers for the function return values.
1565  addOncePattern<calyx::BuildReturnRegs>(loweringPatterns, patternState,
1566  funcMap, *loweringState);
1567 
1568  /// This pattern creates registers for iteration arguments of scf.while
1569  /// operations. Additionally, creates a group for assigning the initial
1570  /// value of the iteration argument registers.
1571  addOncePattern<BuildWhileGroups>(loweringPatterns, patternState, funcMap,
1572  *loweringState);
1573 
1574  /// This pattern creates registers for all pipeline stages.
1575  addOncePattern<BuildPipelineRegs>(loweringPatterns, patternState, funcMap,
1576  *loweringState);
1577 
1578  /// This pattern converts operations within basic blocks to Calyx library
1579  /// operators. Combinational operations are assigned inside a
1580  /// calyx::CombGroupOp, and sequential inside calyx::GroupOps.
1581  /// Sequential groups are registered with the Block* of which the operation
1582  /// originated from. This is used during control schedule generation. By
1583  /// having a distinct group for each operation, groups are analogous to SSA
1584  /// values in the source program.
1585  addOncePattern<BuildOpGroups>(loweringPatterns, patternState, funcMap,
1586  *loweringState);
1587 
1588  /// This pattern creates groups for all pipeline stages.
1589  addOncePattern<BuildPipelineGroups>(loweringPatterns, patternState, funcMap,
1590  *loweringState);
1591 
1592  /// This pattern traverses the CFG of the program and generates a control
1593  /// schedule based on the calyx::GroupOp's which were registered for each
1594  /// basic block in the source function.
1595  addOncePattern<BuildControl>(loweringPatterns, patternState, funcMap,
1596  *loweringState);
1597 
1598  /// This pass recursively inlines use-def chains of combinational logic (from
1599  /// non-stateful groups) into groups referenced in the control schedule.
1600  addOncePattern<calyx::InlineCombGroups>(loweringPatterns, patternState,
1601  *loweringState);
1602 
1603  /// This pattern performs various SSA replacements that must be done
1604  /// after control generation.
1605  addOncePattern<LateSSAReplacement>(loweringPatterns, patternState, funcMap,
1606  *loweringState);
1607 
1608  /// Eliminate any unused combinational groups. This is done before
1609  /// calyx::RewriteMemoryAccesses to avoid inferring slice components for
1610  /// groups that will be removed.
1611  addGreedyPattern<calyx::EliminateUnusedCombGroups>(loweringPatterns);
1612 
1613  /// This pattern rewrites accesses to memories which are too wide due to
1614  /// index types being converted to a fixed-width integer type.
1615  addOncePattern<calyx::RewriteMemoryAccesses>(loweringPatterns, patternState,
1616  *loweringState);
1617 
1618  /// This pattern removes the source FuncOp which has now been converted into
1619  /// a Calyx component.
1620  addOncePattern<CleanupFuncOps>(loweringPatterns, patternState, funcMap,
1621  *loweringState);
1622 
1623  /// Sequentially apply each lowering pattern.
1624  for (auto &pat : loweringPatterns) {
1625  LogicalResult partialPatternRes = runPartialPattern(
1626  pat.pattern,
1627  /*runOnce=*/pat.strategy == LoweringPattern::Strategy::Once);
1628  if (succeeded(partialPatternRes))
1629  continue;
1630  signalPassFailure();
1631  return;
1632  }
1633 
1634  //===----------------------------------------------------------------------===//
1635  // Cleanup patterns
1636  //===----------------------------------------------------------------------===//
1637  RewritePatternSet cleanupPatterns(&getContext());
1638  cleanupPatterns.add<calyx::MultipleGroupDonePattern,
1639  calyx::NonTerminatingGroupDonePattern>(&getContext());
1640  if (failed(applyPatternsAndFoldGreedily(getOperation(),
1641  std::move(cleanupPatterns)))) {
1642  signalPassFailure();
1643  return;
1644  }
1645 
1646  if (ciderSourceLocationMetadata) {
1647  // Debugging information for the Cider debugger.
1648  // Reference: https://docs.calyxir.org/debug/cider.html
1649  SmallVector<Attribute, 16> sourceLocations;
1650  getOperation()->walk([&](calyx::ComponentOp component) {
1651  return getCiderSourceLocationMetadata(component, sourceLocations);
1652  });
1653 
1654  MLIRContext *context = getOperation()->getContext();
1655  getOperation()->setAttr("calyx.metadata",
1656  ArrayAttr::get(context, sourceLocations));
1657  }
1658 }
1659 
1660 } // namespace pipelinetocalyx
1661 
1662 //===----------------------------------------------------------------------===//
1663 // Pass initialization
1664 //===----------------------------------------------------------------------===//
1665 
1666 std::unique_ptr<OperationPass<ModuleOp>> createLoopScheduleToCalyxPass() {
1667  return std::make_unique<pipelinetocalyx::LoopScheduleToCalyxPass>();
1668 }
1669 
1670 } // 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
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...
LogicalResult buildCFGControl(DenseSet< Block * > path, PatternRewriter &rewriter, mlir::Block *parentCtrlBlock, mlir::Block *preBlock, mlir::Block *block) const
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 ...
LogicalResult scheduleBasicBlock(PatternRewriter &rewriter, const DenseSet< Block * > &path, mlir::Block *parentCtrlBlock, mlir::Block *block) const
Sequentially schedules the groups that registered themselves with 'block'.
calyx::WhileOp buildWhileCtrlOp(PipelineWhileOp whileOp, SmallVector< calyx::GroupOp > initGroups, PatternRewriter &rewriter) const
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
Iterate through the operations of a source function and instantiate components or primitives based on...
LogicalResult buildLibraryOp(PatternRewriter &rewriter, TSrcOp op) const
buildLibraryOp which provides in- and output types based on the operands and results of the op argume...
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...
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.
LogicalResult buildLibraryBinaryPipeOp(PatternRewriter &rewriter, TSrcOp op, TOpType opPipe, Value out) const
buildLibraryBinaryPipeOp will build a TCalyxLibBinaryPipeOp, to deal with MulIOp, DivUIOp and RemUIOp...
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
TGroupOp createGroupForOp(PatternRewriter &rewriter, Operation *op) const
Creates a group named by the basic block which the input op resides in.
Builds groups for assigning registers for pipeline stages.
calyx::GroupOp replaceGroupRegister(calyx::GroupInterface evaluatingGroup, calyx::RegisterOp pipelineRegister, PatternRewriter &rewriter) const
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
LogicalResult buildStageGroups(LoopSchedulePipelineOp whileOp, LoopSchedulePipelineStageOp stage, PatternRewriter &rewriter) const
calyx::GroupOp convertCombToSeqGroup(calyx::CombGroupOp combGroup, calyx::RegisterOp pipelineRegister, Value value, PatternRewriter &rewriter) const
Builds registers for each pipeline stage in the program.
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
In BuildWhileGroups, a register is created for each iteration argumenet of the while op.
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
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.
LateSSAReplacement contains various functions for replacing SSA values that were not replaced during ...
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &) const override
void addOncePattern(SmallVectorImpl< LoweringPattern > &patterns, PatternArgs &&...args)
'Once' patterns are expected to take an additional LogicalResult& argument, to forward their result s...
LogicalResult labelEntryPoint(StringRef topLevelFunction)
Labels the entry point of a Calyx program.
void addGreedyPattern(SmallVectorImpl< LoweringPattern > &patterns, PatternArgs &&...args)
LogicalResult setTopLevelFunction(mlir::ModuleOp moduleOp, std::string &topLevelFunction)
LogicalResult runPartialPattern(RewritePatternSet &pattern, bool runOnce)
Holds additional information required for scheduling Pipeline pipelines.
void createPipelinePrologue(Operation *op, PatternRewriter &rewriter)
Create the pipeline prologue.
SmallVector< SmallVector< StringAttr > > getPipelinePrologue(Operation *op)
Get the pipeline prologue.
const DenseMap< unsigned, calyx::RegisterOp > & getPipelineRegs(Operation *stage)
Return a mapping of stage result indices to pipeline registers.
std::optional< TGroupOp > getNonPipelinedGroupFrom(Operation *op)
Returns the group registered for this non-pipelined value, and None otherwise.
void addPipelineReg(Operation *stage, calyx::RegisterOp reg, unsigned idx)
Register reg as being the idx'th pipeline register for the stage.
void addPipelineEpilogue(Operation *op, SmallVector< StringAttr > groupNames)
Add a stage's groups to the pipeline epilogue.
DenseMap< Operation *, calyx::GroupInterface > operationToGroup
A mapping between operations and the group to which it was assigned.
void createPipelineEpilogue(Operation *op, PatternRewriter &rewriter)
Create the pipeline epilogue.
void addPipelinePrologue(Operation *op, SmallVector< StringAttr > groupNames)
Add a stage's groups to the pipeline prologue.
void registerNonPipelineOperations(Operation *op, calyx::GroupInterface group)
Registers operations that may be used in a pipeline, but does not produce a value to be used in a fur...
DenseMap< Operation *, SmallVector< SmallVector< StringAttr > > > pipelineEpilogue
A mapping from pipeline ops to a vector of vectors of group names that constitute the pipeline epilog...
DenseMap< Operation *, SmallVector< SmallVector< StringAttr > > > pipelinePrologue
A mapping from pipeline ops to a vector of vectors of group names that constitute the pipeline prolog...
DenseMap< Operation *, DenseMap< unsigned, calyx::RegisterOp > > pipelineRegs
A mapping from pipeline stages to their registers.
Block::BlockArgListType getBodyArgs() override
std::optional< int64_t > getBound() override
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition: CalyxOps.cpp:54
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)
static LogicalResult buildAllocOp(ComponentLoweringState &componentState, PatternRewriter &rewriter, TAllocOp allocOp)
std::variant< calyx::GroupOp, PipelineScheduleable > Scheduleable
A variant of types representing scheduleable operations.
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21
std::unique_ptr< OperationPass< ModuleOp > > createLoopScheduleToCalyxPass()
Create a LoopSchedule 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 > done
std::optional< Value > writeEn
std::optional< Value > writeData
std::optional< Value > readData
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:85
Creates a new Calyx component for each FuncOp in the program.
LogicalResult partiallyLowerFuncToComp(FuncOp funcOp, PatternRewriter &rewriter) const override
SmallVector< calyx::GroupOp > initGroups
The group(s) to schedule before the while operation These groups should set the initial value(s) of t...
PipelineWhileOp whileOp
While operation to schedule.