CIRCT  18.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  rewriter.create<calyx::GroupDoneOp>(storeOp.getLoc(),
479  memoryInterface.writeDone());
480 
481  getState<ComponentLoweringState>().registerNonPipelineOperations(storeOp,
482  group);
483 
484  return success();
485 }
486 
487 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
488  MulIOp mul) const {
489  Location loc = mul.getLoc();
490  Type width = mul.getResult().getType(), one = rewriter.getI1Type();
491  auto mulPipe =
492  getState<ComponentLoweringState>()
493  .getNewLibraryOpInstance<calyx::MultPipeLibOp>(
494  rewriter, loc, {one, one, one, width, width, width, one});
495  return buildLibraryBinaryPipeOp<calyx::MultPipeLibOp>(
496  rewriter, mul, mulPipe,
497  /*out=*/mulPipe.getOut());
498 }
499 
500 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
501  DivUIOp div) const {
502  Location loc = div.getLoc();
503  Type width = div.getResult().getType(), one = rewriter.getI1Type();
504  auto divPipe =
505  getState<ComponentLoweringState>()
506  .getNewLibraryOpInstance<calyx::DivUPipeLibOp>(
507  rewriter, loc, {one, one, one, width, width, width, width, one});
508  return buildLibraryBinaryPipeOp<calyx::DivUPipeLibOp>(
509  rewriter, div, divPipe,
510  /*out=*/divPipe.getOut());
511 }
512 
513 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
514  RemUIOp rem) const {
515  Location loc = rem.getLoc();
516  Type width = rem.getResult().getType(), one = rewriter.getI1Type();
517  auto remPipe =
518  getState<ComponentLoweringState>()
519  .getNewLibraryOpInstance<calyx::DivUPipeLibOp>(
520  rewriter, loc, {one, one, one, width, width, width, width, one});
521  return buildLibraryBinaryPipeOp<calyx::DivUPipeLibOp>(
522  rewriter, rem, remPipe,
523  /*out=*/remPipe.getOut());
524 }
525 
526 template <typename TAllocOp>
527 static LogicalResult buildAllocOp(ComponentLoweringState &componentState,
528  PatternRewriter &rewriter, TAllocOp allocOp) {
529  rewriter.setInsertionPointToStart(
530  componentState.getComponentOp().getBodyBlock());
531  MemRefType memtype = allocOp.getType();
532  SmallVector<int64_t> addrSizes;
533  SmallVector<int64_t> sizes;
534  for (int64_t dim : memtype.getShape()) {
535  sizes.push_back(dim);
536  addrSizes.push_back(calyx::handleZeroWidth(dim));
537  }
538  // If memref has no size (e.g., memref<i32>) create a 1 dimensional memory of
539  // size 1.
540  if (sizes.empty() && addrSizes.empty()) {
541  sizes.push_back(1);
542  addrSizes.push_back(1);
543  }
544  auto memoryOp = rewriter.create<calyx::MemoryOp>(
545  allocOp.getLoc(), componentState.getUniqueName("mem"),
546  memtype.getElementType().getIntOrFloatBitWidth(), sizes, addrSizes);
547  // Externalize memories by default. This makes it easier for the native
548  // compiler to provide initialized memories.
549  memoryOp->setAttr("external",
550  IntegerAttr::get(rewriter.getI1Type(), llvm::APInt(1, 1)));
551  componentState.registerMemoryInterface(allocOp.getResult(),
552  calyx::MemoryInterface(memoryOp));
553  return success();
554 }
555 
556 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
557  memref::AllocOp allocOp) const {
558  return buildAllocOp(getState<ComponentLoweringState>(), rewriter, allocOp);
559 }
560 
561 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
562  memref::AllocaOp allocOp) const {
563  return buildAllocOp(getState<ComponentLoweringState>(), rewriter, allocOp);
564 }
565 
566 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
567  LoopScheduleTerminatorOp term) const {
568  if (term.getOperands().size() == 0)
569  return success();
570 
571  // Replace the pipeline's result(s) with the terminator's results.
572  auto *pipeline = term->getParentOp();
573  for (size_t i = 0, e = pipeline->getNumResults(); i < e; ++i)
574  pipeline->getResult(i).replaceAllUsesWith(term.getResults()[i]);
575 
576  return success();
577 }
578 
579 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
580  BranchOpInterface brOp) const {
581  /// Branch argument passing group creation
582  /// Branch operands are passed through registers. In BuildBasicBlockRegs we
583  /// created registers for all branch arguments of each block. We now
584  /// create groups for assigning values to these registers.
585  Block *srcBlock = brOp->getBlock();
586  for (auto succBlock : enumerate(brOp->getSuccessors())) {
587  auto succOperands = brOp.getSuccessorOperands(succBlock.index());
588  if (succOperands.empty())
589  continue;
590  // Create operand passing group
591  std::string groupName = loweringState().blockName(srcBlock) + "_to_" +
592  loweringState().blockName(succBlock.value());
593  auto groupOp = calyx::createGroup<calyx::GroupOp>(rewriter, getComponent(),
594  brOp.getLoc(), groupName);
595  // Fetch block argument registers associated with the basic block
596  auto dstBlockArgRegs =
597  getState<ComponentLoweringState>().getBlockArgRegs(succBlock.value());
598  // Create register assignment for each block argument
599  for (auto arg : enumerate(succOperands.getForwardedOperands())) {
600  auto reg = dstBlockArgRegs[arg.index()];
602  rewriter, groupOp,
603  getState<ComponentLoweringState>().getComponentOp(), reg,
604  arg.value());
605  }
606  /// Register the group as a block argument group, to be executed
607  /// when entering the successor block from this block (srcBlock).
608  getState<ComponentLoweringState>().addBlockArgGroup(
609  srcBlock, succBlock.value(), groupOp);
610  }
611  return success();
612 }
613 
614 /// For each return statement, we create a new group for assigning to the
615 /// previously created return value registers.
616 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
617  ReturnOp retOp) const {
618  if (retOp.getNumOperands() == 0)
619  return success();
620 
621  std::string groupName =
622  getState<ComponentLoweringState>().getUniqueName("ret_assign");
623  auto groupOp = calyx::createGroup<calyx::GroupOp>(rewriter, getComponent(),
624  retOp.getLoc(), groupName);
625  for (auto op : enumerate(retOp.getOperands())) {
626  auto reg = getState<ComponentLoweringState>().getReturnReg(op.index());
628  rewriter, groupOp, getState<ComponentLoweringState>().getComponentOp(),
629  reg, op.value());
630  }
631  /// Schedule group for execution for when executing the return op block.
632  getState<ComponentLoweringState>().addBlockScheduleable(retOp->getBlock(),
633  groupOp);
634  return success();
635 }
636 
637 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
638  arith::ConstantOp constOp) const {
639  /// Move constant operations to the compOp body as hw::ConstantOp's.
640  APInt value;
641  calyx::matchConstantOp(constOp, value);
642  auto hwConstOp = rewriter.replaceOpWithNewOp<hw::ConstantOp>(constOp, value);
643  hwConstOp->moveAfter(getComponent().getBodyBlock(),
644  getComponent().getBodyBlock()->begin());
645  return success();
646 }
647 
648 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
649  AddIOp op) const {
650  return buildLibraryOp<calyx::CombGroupOp, calyx::AddLibOp>(rewriter, op);
651 }
652 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
653  SubIOp op) const {
654  return buildLibraryOp<calyx::CombGroupOp, calyx::SubLibOp>(rewriter, op);
655 }
656 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
657  ShRUIOp op) const {
658  return buildLibraryOp<calyx::CombGroupOp, calyx::RshLibOp>(rewriter, op);
659 }
660 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
661  ShRSIOp op) const {
662  return buildLibraryOp<calyx::CombGroupOp, calyx::SrshLibOp>(rewriter, op);
663 }
664 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
665  ShLIOp op) const {
666  return buildLibraryOp<calyx::CombGroupOp, calyx::LshLibOp>(rewriter, op);
667 }
668 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
669  AndIOp op) const {
670  return buildLibraryOp<calyx::CombGroupOp, calyx::AndLibOp>(rewriter, op);
671 }
672 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
673  OrIOp op) const {
674  return buildLibraryOp<calyx::CombGroupOp, calyx::OrLibOp>(rewriter, op);
675 }
676 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
677  XOrIOp op) const {
678  return buildLibraryOp<calyx::CombGroupOp, calyx::XorLibOp>(rewriter, op);
679 }
680 
681 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
682  CmpIOp op) const {
683  switch (op.getPredicate()) {
684  case CmpIPredicate::eq:
685  return buildLibraryOp<calyx::CombGroupOp, calyx::EqLibOp>(rewriter, op);
686  case CmpIPredicate::ne:
687  return buildLibraryOp<calyx::CombGroupOp, calyx::NeqLibOp>(rewriter, op);
688  case CmpIPredicate::uge:
689  return buildLibraryOp<calyx::CombGroupOp, calyx::GeLibOp>(rewriter, op);
690  case CmpIPredicate::ult:
691  return buildLibraryOp<calyx::CombGroupOp, calyx::LtLibOp>(rewriter, op);
692  case CmpIPredicate::ugt:
693  return buildLibraryOp<calyx::CombGroupOp, calyx::GtLibOp>(rewriter, op);
694  case CmpIPredicate::ule:
695  return buildLibraryOp<calyx::CombGroupOp, calyx::LeLibOp>(rewriter, op);
696  case CmpIPredicate::sge:
697  return buildLibraryOp<calyx::CombGroupOp, calyx::SgeLibOp>(rewriter, op);
698  case CmpIPredicate::slt:
699  return buildLibraryOp<calyx::CombGroupOp, calyx::SltLibOp>(rewriter, op);
700  case CmpIPredicate::sgt:
701  return buildLibraryOp<calyx::CombGroupOp, calyx::SgtLibOp>(rewriter, op);
702  case CmpIPredicate::sle:
703  return buildLibraryOp<calyx::CombGroupOp, calyx::SleLibOp>(rewriter, op);
704  }
705  llvm_unreachable("unsupported comparison predicate");
706 }
707 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
708  TruncIOp op) const {
709  return buildLibraryOp<calyx::CombGroupOp, calyx::SliceLibOp>(
710  rewriter, op, {op.getOperand().getType()}, {op.getType()});
711 }
712 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
713  ExtUIOp op) const {
714  return buildLibraryOp<calyx::CombGroupOp, calyx::PadLibOp>(
715  rewriter, op, {op.getOperand().getType()}, {op.getType()});
716 }
717 
718 LogicalResult BuildOpGroups::buildOp(PatternRewriter &rewriter,
719  IndexCastOp op) const {
720  Type sourceType = calyx::convIndexType(rewriter, op.getOperand().getType());
721  Type targetType = calyx::convIndexType(rewriter, op.getResult().getType());
722  unsigned targetBits = targetType.getIntOrFloatBitWidth();
723  unsigned sourceBits = sourceType.getIntOrFloatBitWidth();
724  LogicalResult res = success();
725 
726  if (targetBits == sourceBits) {
727  /// Drop the index cast and replace uses of the target value with the source
728  /// value.
729  op.getResult().replaceAllUsesWith(op.getOperand());
730  } else {
731  /// pad/slice the source operand.
732  if (sourceBits > targetBits)
733  res = buildLibraryOp<calyx::CombGroupOp, calyx::SliceLibOp>(
734  rewriter, op, {sourceType}, {targetType});
735  else
736  res = buildLibraryOp<calyx::CombGroupOp, calyx::PadLibOp>(
737  rewriter, op, {sourceType}, {targetType});
738  }
739  rewriter.eraseOp(op);
740  return res;
741 }
742 
743 /// Creates a new Calyx component for each FuncOp in the program.
745  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
746 
747  LogicalResult
749  PatternRewriter &rewriter) const override {
750  /// Maintain a mapping between funcOp input arguments and the port index
751  /// which the argument will eventually map to.
752  DenseMap<Value, unsigned> funcOpArgRewrites;
753 
754  /// Maintain a mapping between funcOp output indexes and the component
755  /// output port index which the return value will eventually map to.
756  DenseMap<unsigned, unsigned> funcOpResultMapping;
757 
758  /// Maintain a mapping between an external memory argument (identified by a
759  /// memref) and eventual component input- and output port indices that will
760  /// map to the memory ports. The pair denotes the start index of the memory
761  /// ports in the in- and output ports of the component. Ports are expected
762  /// to be ordered in the same manner as they are added by
763  /// calyx::appendPortsForExternalMemref.
764  DenseMap<Value, std::pair<unsigned, unsigned>> extMemoryCompPortIndices;
765 
766  /// Create I/O ports. Maintain separate in/out port vectors to determine
767  /// which port index each function argument will eventually map to.
768  SmallVector<calyx::PortInfo> inPorts, outPorts;
769  FunctionType funcType = funcOp.getFunctionType();
770  unsigned extMemCounter = 0;
771  for (auto arg : enumerate(funcOp.getArguments())) {
772  if (arg.value().getType().isa<MemRefType>()) {
773  /// External memories
774  auto memName =
775  "ext_mem" + std::to_string(extMemoryCompPortIndices.size());
776  extMemoryCompPortIndices[arg.value()] = {inPorts.size(),
777  outPorts.size()};
778  calyx::appendPortsForExternalMemref(rewriter, memName, arg.value(),
779  extMemCounter++, inPorts, outPorts);
780  } else {
781  /// Single-port arguments
782  auto inName = "in" + std::to_string(arg.index());
783  funcOpArgRewrites[arg.value()] = inPorts.size();
784  inPorts.push_back(calyx::PortInfo{
785  rewriter.getStringAttr(inName),
786  calyx::convIndexType(rewriter, arg.value().getType()),
788  DictionaryAttr::get(rewriter.getContext(), {})});
789  }
790  }
791  for (auto res : enumerate(funcType.getResults())) {
792  funcOpResultMapping[res.index()] = outPorts.size();
793  outPorts.push_back(calyx::PortInfo{
794  rewriter.getStringAttr("out" + std::to_string(res.index())),
795  calyx::convIndexType(rewriter, res.value()), calyx::Direction::Output,
796  DictionaryAttr::get(rewriter.getContext(), {})});
797  }
798 
799  /// We've now recorded all necessary indices. Merge in- and output ports
800  /// and add the required mandatory component ports.
801  auto ports = inPorts;
802  llvm::append_range(ports, outPorts);
803  calyx::addMandatoryComponentPorts(rewriter, ports);
804 
805  /// Create a calyx::ComponentOp corresponding to the to-be-lowered function.
806  auto compOp = rewriter.create<calyx::ComponentOp>(
807  funcOp.getLoc(), rewriter.getStringAttr(funcOp.getSymName()), ports);
808 
809  /// Mark this component as the toplevel.
810  compOp->setAttr("toplevel", rewriter.getUnitAttr());
811 
812  /// Store the function-to-component mapping.
813  functionMapping[funcOp] = compOp;
814  auto *compState = loweringState().getState<ComponentLoweringState>(compOp);
815  compState->setFuncOpResultMapping(funcOpResultMapping);
816 
817  /// Rewrite funcOp SSA argument values to the CompOp arguments.
818  for (auto &mapping : funcOpArgRewrites)
819  mapping.getFirst().replaceAllUsesWith(
820  compOp.getArgument(mapping.getSecond()));
821 
822  /// Register external memories
823  for (auto extMemPortIndices : extMemoryCompPortIndices) {
824  /// Create a mapping for the in- and output ports using the Calyx memory
825  /// port structure.
826  calyx::MemoryPortsImpl extMemPorts;
827  unsigned inPortsIt = extMemPortIndices.getSecond().first;
828  unsigned outPortsIt = extMemPortIndices.getSecond().second +
829  compOp.getInputPortInfo().size();
830  extMemPorts.readData = compOp.getArgument(inPortsIt++);
831  extMemPorts.writeDone = compOp.getArgument(inPortsIt);
832  extMemPorts.writeData = compOp.getArgument(outPortsIt++);
833  unsigned nAddresses = extMemPortIndices.getFirst()
834  .getType()
835  .cast<MemRefType>()
836  .getShape()
837  .size();
838  for (unsigned j = 0; j < nAddresses; ++j)
839  extMemPorts.addrPorts.push_back(compOp.getArgument(outPortsIt++));
840  extMemPorts.writeEn = compOp.getArgument(outPortsIt);
841 
842  /// Register the external memory ports as a memory interface within the
843  /// component.
844  compState->registerMemoryInterface(extMemPortIndices.getFirst(),
845  calyx::MemoryInterface(extMemPorts));
846  }
847 
848  return success();
849  }
850 };
851 
852 /// In BuildWhileGroups, a register is created for each iteration argumenet of
853 /// the while op. These registers are then written to on the while op
854 /// terminating yield operation alongside before executing the whileOp in the
855 /// schedule, to set the initial values of the argument registers.
857  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
858 
859  LogicalResult
861  PatternRewriter &rewriter) const override {
862  LogicalResult res = success();
863  funcOp.walk([&](Operation *op) {
864  if (!isa<LoopSchedulePipelineOp>(op))
865  return WalkResult::advance();
866 
867  PipelineWhileOp whileOp(cast<LoopSchedulePipelineOp>(op));
868 
869  getState<ComponentLoweringState>().setUniqueName(whileOp.getOperation(),
870  "while");
871 
872  /// Create iteration argument registers.
873  /// The iteration argument registers will be referenced:
874  /// - In the "before" part of the while loop, calculating the conditional,
875  /// - In the "after" part of the while loop,
876  /// - Outside the while loop, rewriting the while loop return values.
877  for (auto arg : enumerate(whileOp.getBodyArgs())) {
878  std::string name = getState<ComponentLoweringState>()
879  .getUniqueName(whileOp.getOperation())
880  .str() +
881  "_arg" + std::to_string(arg.index());
882  auto reg =
883  createRegister(arg.value().getLoc(), rewriter, getComponent(),
884  arg.value().getType().getIntOrFloatBitWidth(), name);
885  getState<ComponentLoweringState>().addLoopIterReg(whileOp, reg,
886  arg.index());
887  arg.value().replaceAllUsesWith(reg.getOut());
888 
889  /// Also replace uses in the "before" region of the while loop
890  whileOp.getConditionBlock()
891  ->getArgument(arg.index())
892  .replaceAllUsesWith(reg.getOut());
893  }
894 
895  /// Create iter args initial value assignment group(s), one per register.
896  SmallVector<calyx::GroupOp> initGroups;
897  auto numOperands = whileOp.getOperation()->getNumOperands();
898  for (size_t i = 0; i < numOperands; ++i) {
899  auto initGroupOp =
900  getState<ComponentLoweringState>().buildLoopIterArgAssignments(
901  rewriter, whileOp,
902  getState<ComponentLoweringState>().getComponentOp(),
903  getState<ComponentLoweringState>().getUniqueName(
904  whileOp.getOperation()) +
905  "_init_" + std::to_string(i),
906  whileOp.getOperation()->getOpOperand(i));
907  initGroups.push_back(initGroupOp);
908  }
909 
910  /// Add the while op to the list of scheduleable things in the current
911  /// block.
912  getState<ComponentLoweringState>().addBlockScheduleable(
913  whileOp.getOperation()->getBlock(), PipelineScheduleable{
914  whileOp,
915  initGroups,
916  });
917  return WalkResult::advance();
918  });
919  return res;
920  }
921 };
922 
923 /// Builds registers for each pipeline stage in the program.
925  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
926 
927  LogicalResult
929  PatternRewriter &rewriter) const override {
930  funcOp.walk([&](LoopScheduleRegisterOp op) {
931  // Condition registers are handled in BuildWhileGroups.
932  auto *parent = op->getParentOp();
933  auto stage = dyn_cast<LoopSchedulePipelineStageOp>(parent);
934  if (!stage)
935  return;
936 
937  // Create a register for each stage.
938  for (auto &operand : op->getOpOperands()) {
939  unsigned i = operand.getOperandNumber();
940  // Iter args are created in BuildWhileGroups, so just mark the iter arg
941  // register as the appropriate pipeline register.
942  Value stageResult = stage.getResult(i);
943  bool isIterArg = false;
944  for (auto &use : stageResult.getUses()) {
945  if (auto term = dyn_cast<LoopScheduleTerminatorOp>(use.getOwner())) {
946  if (use.getOperandNumber() < term.getIterArgs().size()) {
947  PipelineWhileOp whileOp(
948  dyn_cast<LoopSchedulePipelineOp>(stage->getParentOp()));
949  auto reg = getState<ComponentLoweringState>().getLoopIterReg(
950  whileOp, use.getOperandNumber());
951  getState<ComponentLoweringState>().addPipelineReg(stage, reg, i);
952  isIterArg = true;
953  }
954  }
955  }
956  if (isIterArg)
957  continue;
958 
959  // Create a register for passing this result to later stages.
960  Value value = operand.get();
961  Type resultType = value.getType();
962  assert(resultType.isa<IntegerType>() &&
963  "unsupported pipeline result type");
964  auto name = SmallString<20>("stage_");
965  name += std::to_string(stage.getStageNumber());
966  name += "_register_";
967  name += std::to_string(i);
968  unsigned width = resultType.getIntOrFloatBitWidth();
969  auto reg = createRegister(value.getLoc(), rewriter, getComponent(),
970  width, name);
971  getState<ComponentLoweringState>().addPipelineReg(stage, reg, i);
972 
973  // Note that we do not use replace all uses with here as in
974  // BuildBasicBlockRegs. Instead, we wait until after BuildOpGroups, and
975  // replace all uses inside BuildPipelineGroups, once the pipeline
976  // register created here has been assigned to.
977  }
978  });
979  return success();
980  }
981 };
982 
983 /// Builds groups for assigning registers for pipeline stages.
985  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
986 
987  LogicalResult
989  PatternRewriter &rewriter) const override {
990  for (auto pipeline : funcOp.getOps<LoopSchedulePipelineOp>())
991  for (auto stage :
992  pipeline.getStagesBlock().getOps<LoopSchedulePipelineStageOp>())
993  if (failed(buildStageGroups(pipeline, stage, rewriter)))
994  return failure();
995 
996  return success();
997  }
998 
999  LogicalResult buildStageGroups(LoopSchedulePipelineOp whileOp,
1000  LoopSchedulePipelineStageOp stage,
1001  PatternRewriter &rewriter) const {
1002  // Collect pipeline registers for stage.
1003  auto pipelineRegisters =
1004  getState<ComponentLoweringState>().getPipelineRegs(stage);
1005  // Get the number of pipeline stages in the stages block, excluding the
1006  // terminator. The verifier guarantees there is at least one stage followed
1007  // by a terminator.
1008  size_t numStages = whileOp.getStagesBlock().getOperations().size() - 1;
1009  assert(numStages > 0);
1010 
1011  // Collect group names for the prologue or epilogue.
1012  SmallVector<StringAttr> prologueGroups, epilogueGroups;
1013 
1014  auto updatePrologueAndEpilogue = [&](calyx::GroupOp group) {
1015  // Mark the group for scheduling in the pipeline's block.
1016  getState<ComponentLoweringState>().addBlockScheduleable(stage->getBlock(),
1017  group);
1018 
1019  // Add the group to the prologue or epilogue for this stage as
1020  // necessary. The goal is to fill the pipeline so it will be in steady
1021  // state after the prologue, and drain the pipeline from steady state in
1022  // the epilogue. Every stage but the last should have its groups in the
1023  // prologue, and every stage but the first should have its groups in the
1024  // epilogue.
1025  unsigned stageNumber = stage.getStageNumber();
1026  if (stageNumber < numStages - 1)
1027  prologueGroups.push_back(group.getSymNameAttr());
1028  if (stageNumber > 0)
1029  epilogueGroups.push_back(group.getSymNameAttr());
1030  };
1031 
1032  MutableArrayRef<OpOperand> operands =
1033  stage.getBodyBlock().getTerminator()->getOpOperands();
1034  bool isStageWithNoPipelinedValues =
1035  operands.empty() && !stage.getBodyBlock().empty();
1036  if (isStageWithNoPipelinedValues) {
1037  // Covers the case where there are no values that need to be passed
1038  // through to the next stage, e.g., some intermediary store.
1039  for (auto &op : stage.getBodyBlock())
1040  if (auto group = getState<ComponentLoweringState>()
1041  .getNonPipelinedGroupFrom<calyx::GroupOp>(&op))
1042  updatePrologueAndEpilogue(*group);
1043  }
1044 
1045  for (auto &operand : operands) {
1046  unsigned i = operand.getOperandNumber();
1047  Value value = operand.get();
1048 
1049  // Get the pipeline register for that result.
1050  auto pipelineRegister = pipelineRegisters[i];
1051 
1052  // Get the evaluating group for that value.
1053  calyx::GroupInterface evaluatingGroup =
1054  getState<ComponentLoweringState>().getEvaluatingGroup(value);
1055 
1056  // Remember the final group for this stage result.
1057  calyx::GroupOp group;
1058 
1059  // Stitch the register in, depending on whether the group was
1060  // combinational or sequential.
1061  if (auto combGroup =
1062  dyn_cast<calyx::CombGroupOp>(evaluatingGroup.getOperation()))
1063  group =
1064  convertCombToSeqGroup(combGroup, pipelineRegister, value, rewriter);
1065  else
1066  group =
1067  replaceGroupRegister(evaluatingGroup, pipelineRegister, rewriter);
1068 
1069  // Replace the stage result uses with the register out.
1070  stage.getResult(i).replaceAllUsesWith(pipelineRegister.getOut());
1071 
1072  updatePrologueAndEpilogue(group);
1073  }
1074 
1075  // Append the stage to the prologue or epilogue list of stages if any groups
1076  // were added for this stage. We append a list of groups for each stage, so
1077  // we can group by stage later, when we generate the schedule.
1078  if (!prologueGroups.empty())
1079  getState<ComponentLoweringState>().addPipelinePrologue(whileOp,
1080  prologueGroups);
1081  if (!epilogueGroups.empty())
1082  getState<ComponentLoweringState>().addPipelineEpilogue(whileOp,
1083  epilogueGroups);
1084 
1085  return success();
1086  }
1087 
1088  calyx::GroupOp convertCombToSeqGroup(calyx::CombGroupOp combGroup,
1089  calyx::RegisterOp pipelineRegister,
1090  Value value,
1091  PatternRewriter &rewriter) const {
1092  // Create a sequential group and replace the comb group.
1093  PatternRewriter::InsertionGuard g(rewriter);
1094  rewriter.setInsertionPoint(combGroup);
1095  auto group = rewriter.create<calyx::GroupOp>(combGroup.getLoc(),
1096  combGroup.getName());
1097  rewriter.cloneRegionBefore(combGroup.getBodyRegion(),
1098  &group.getBody().front());
1099  group.getBodyRegion().back().erase();
1100  rewriter.eraseOp(combGroup);
1101 
1102  // Stitch evaluating group to register.
1104  rewriter, group, getState<ComponentLoweringState>().getComponentOp(),
1105  pipelineRegister, value);
1106 
1107  // Mark the new group as the evaluating group.
1108  for (auto assign : group.getOps<calyx::AssignOp>())
1109  getState<ComponentLoweringState>().registerEvaluatingGroup(
1110  assign.getSrc(), group);
1111 
1112  return group;
1113  }
1114 
1115  calyx::GroupOp replaceGroupRegister(calyx::GroupInterface evaluatingGroup,
1116  calyx::RegisterOp pipelineRegister,
1117  PatternRewriter &rewriter) const {
1118  auto group = cast<calyx::GroupOp>(evaluatingGroup.getOperation());
1119 
1120  // Get the group and register that is temporarily being written to.
1121  auto doneOp = group.getDoneOp();
1122  auto tempReg =
1123  cast<calyx::RegisterOp>(doneOp.getSrc().cast<OpResult>().getOwner());
1124  auto tempIn = tempReg.getIn();
1125  auto tempWriteEn = tempReg.getWriteEn();
1126 
1127  // Replace the register write with a write to the pipeline register.
1128  for (auto assign : group.getOps<calyx::AssignOp>()) {
1129  if (assign.getDest() == tempIn)
1130  assign.getDestMutable().assign(pipelineRegister.getIn());
1131  else if (assign.getDest() == tempWriteEn)
1132  assign.getDestMutable().assign(pipelineRegister.getWriteEn());
1133  }
1134  doneOp.getSrcMutable().assign(pipelineRegister.getDone());
1135 
1136  // Remove the old register completely.
1137  rewriter.eraseOp(tempReg);
1138 
1139  return group;
1140  }
1141 };
1142 
1143 /// Builds a control schedule by traversing the CFG of the function and
1144 /// associating this with the previously created groups.
1145 /// For simplicity, the generated control flow is expanded for all possible
1146 /// paths in the input DAG. This elaborated control flow is later reduced in
1147 /// the runControlFlowSimplification passes.
1149  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1150 
1151  LogicalResult
1153  PatternRewriter &rewriter) const override {
1154  auto *entryBlock = &funcOp.getBlocks().front();
1155  rewriter.setInsertionPointToStart(
1156  getComponent().getControlOp().getBodyBlock());
1157  auto topLevelSeqOp = rewriter.create<calyx::SeqOp>(funcOp.getLoc());
1158  DenseSet<Block *> path;
1159  return buildCFGControl(path, rewriter, topLevelSeqOp.getBodyBlock(),
1160  nullptr, entryBlock);
1161  }
1162 
1163 private:
1164  /// Sequentially schedules the groups that registered themselves with
1165  /// 'block'.
1166  LogicalResult scheduleBasicBlock(PatternRewriter &rewriter,
1167  const DenseSet<Block *> &path,
1168  mlir::Block *parentCtrlBlock,
1169  mlir::Block *block) const {
1170  auto compBlockScheduleables =
1171  getState<ComponentLoweringState>().getBlockScheduleables(block);
1172  auto loc = block->front().getLoc();
1173 
1174  if (compBlockScheduleables.size() > 1) {
1175  auto seqOp = rewriter.create<calyx::SeqOp>(loc);
1176  parentCtrlBlock = seqOp.getBodyBlock();
1177  }
1178 
1179  for (auto &group : compBlockScheduleables) {
1180  rewriter.setInsertionPointToEnd(parentCtrlBlock);
1181  if (auto groupPtr = std::get_if<calyx::GroupOp>(&group); groupPtr) {
1182  rewriter.create<calyx::EnableOp>(groupPtr->getLoc(),
1183  groupPtr->getSymName());
1184  } else if (auto *pipeSchedPtr = std::get_if<PipelineScheduleable>(&group);
1185  pipeSchedPtr) {
1186  auto &whileOp = pipeSchedPtr->whileOp;
1187 
1188  auto whileCtrlOp =
1189  buildWhileCtrlOp(whileOp, pipeSchedPtr->initGroups, rewriter);
1190  rewriter.setInsertionPointToEnd(whileCtrlOp.getBodyBlock());
1191  auto whileBodyOp =
1192  rewriter.create<calyx::ParOp>(whileOp.getOperation()->getLoc());
1193  rewriter.setInsertionPointToEnd(whileBodyOp.getBodyBlock());
1194 
1195  /// Schedule pipeline stages in the parallel group directly.
1196  auto bodyBlockScheduleables =
1197  getState<ComponentLoweringState>().getBlockScheduleables(
1198  whileOp.getBodyBlock());
1199  for (auto &group : bodyBlockScheduleables)
1200  if (auto *groupPtr = std::get_if<calyx::GroupOp>(&group); groupPtr)
1201  rewriter.create<calyx::EnableOp>(groupPtr->getLoc(),
1202  groupPtr->getSymName());
1203  else
1204  return whileOp.getOperation()->emitError(
1205  "Unsupported block schedulable");
1206 
1207  // Add any prologue or epilogue.
1208  PatternRewriter::InsertionGuard g(rewriter);
1209  rewriter.setInsertionPoint(whileCtrlOp);
1210  getState<ComponentLoweringState>().createPipelinePrologue(
1211  whileOp.getOperation(), rewriter);
1212  rewriter.setInsertionPointAfter(whileCtrlOp);
1213  getState<ComponentLoweringState>().createPipelineEpilogue(
1214  whileOp.getOperation(), rewriter);
1215  } else
1216  llvm_unreachable("Unknown scheduleable");
1217  }
1218  return success();
1219  }
1220 
1221  /// Schedules a block by inserting a branch argument assignment block (if any)
1222  /// before recursing into the scheduling of the block innards.
1223  /// Blocks 'from' and 'to' refer to blocks in the source program.
1224  /// parentCtrlBlock refers to the control block wherein control operations are
1225  /// to be inserted.
1226  LogicalResult schedulePath(PatternRewriter &rewriter,
1227  const DenseSet<Block *> &path, Location loc,
1228  Block *from, Block *to,
1229  Block *parentCtrlBlock) const {
1230  /// Schedule any registered block arguments to be executed before the body
1231  /// of the branch.
1232  rewriter.setInsertionPointToEnd(parentCtrlBlock);
1233  auto preSeqOp = rewriter.create<calyx::SeqOp>(loc);
1234  rewriter.setInsertionPointToEnd(preSeqOp.getBodyBlock());
1235  for (auto barg :
1236  getState<ComponentLoweringState>().getBlockArgGroups(from, to))
1237  rewriter.create<calyx::EnableOp>(barg.getLoc(), barg.getSymName());
1238 
1239  return buildCFGControl(path, rewriter, parentCtrlBlock, from, to);
1240  }
1241 
1242  LogicalResult buildCFGControl(DenseSet<Block *> path,
1243  PatternRewriter &rewriter,
1244  mlir::Block *parentCtrlBlock,
1245  mlir::Block *preBlock,
1246  mlir::Block *block) const {
1247  if (path.count(block) != 0)
1248  return preBlock->getTerminator()->emitError()
1249  << "CFG backedge detected. Loops must be raised to 'scf.while' or "
1250  "'scf.for' operations.";
1251 
1252  rewriter.setInsertionPointToEnd(parentCtrlBlock);
1253  LogicalResult bbSchedResult =
1254  scheduleBasicBlock(rewriter, path, parentCtrlBlock, block);
1255  if (bbSchedResult.failed())
1256  return bbSchedResult;
1257 
1258  path.insert(block);
1259  auto successors = block->getSuccessors();
1260  auto nSuccessors = successors.size();
1261  if (nSuccessors > 0) {
1262  auto brOp = dyn_cast<BranchOpInterface>(block->getTerminator());
1263  assert(brOp);
1264  if (nSuccessors > 1) {
1265  /// TODO(mortbopet): we could choose to support ie. std.switch, but it
1266  /// would probably be easier to just require it to be lowered
1267  /// beforehand.
1268  assert(nSuccessors == 2 &&
1269  "only conditional branches supported for now...");
1270  /// Wrap each branch inside an if/else.
1271  auto cond = brOp->getOperand(0);
1272  auto condGroup = getState<ComponentLoweringState>()
1273  .getEvaluatingGroup<calyx::CombGroupOp>(cond);
1274  auto symbolAttr = FlatSymbolRefAttr::get(
1275  StringAttr::get(getContext(), condGroup.getSymName()));
1276 
1277  auto ifOp = rewriter.create<calyx::IfOp>(
1278  brOp->getLoc(), cond, symbolAttr, /*initializeElseBody=*/true);
1279  rewriter.setInsertionPointToStart(ifOp.getThenBody());
1280  auto thenSeqOp = rewriter.create<calyx::SeqOp>(brOp.getLoc());
1281  rewriter.setInsertionPointToStart(ifOp.getElseBody());
1282  auto elseSeqOp = rewriter.create<calyx::SeqOp>(brOp.getLoc());
1283 
1284  bool trueBrSchedSuccess =
1285  schedulePath(rewriter, path, brOp.getLoc(), block, successors[0],
1286  thenSeqOp.getBodyBlock())
1287  .succeeded();
1288  bool falseBrSchedSuccess = true;
1289  if (trueBrSchedSuccess) {
1290  falseBrSchedSuccess =
1291  schedulePath(rewriter, path, brOp.getLoc(), block, successors[1],
1292  elseSeqOp.getBodyBlock())
1293  .succeeded();
1294  }
1295 
1296  return success(trueBrSchedSuccess && falseBrSchedSuccess);
1297  } else {
1298  /// Schedule sequentially within the current parent control block.
1299  return schedulePath(rewriter, path, brOp.getLoc(), block,
1300  successors.front(), parentCtrlBlock);
1301  }
1302  }
1303  return success();
1304  }
1305 
1306  calyx::WhileOp buildWhileCtrlOp(PipelineWhileOp whileOp,
1307  SmallVector<calyx::GroupOp> initGroups,
1308  PatternRewriter &rewriter) const {
1309  Location loc = whileOp.getLoc();
1310  /// Insert while iter arg initialization group(s). Emit a
1311  /// parallel group to assign one or more registers all at once.
1312  {
1313  PatternRewriter::InsertionGuard g(rewriter);
1314  auto parOp = rewriter.create<calyx::ParOp>(loc);
1315  rewriter.setInsertionPointToStart(parOp.getBodyBlock());
1316  for (calyx::GroupOp group : initGroups)
1317  rewriter.create<calyx::EnableOp>(group.getLoc(), group.getName());
1318  }
1319 
1320  /// Insert the while op itself.
1321  auto cond = whileOp.getConditionValue();
1322  auto condGroup = getState<ComponentLoweringState>()
1323  .getEvaluatingGroup<calyx::CombGroupOp>(cond);
1324  auto symbolAttr = FlatSymbolRefAttr::get(
1325  StringAttr::get(getContext(), condGroup.getSymName()));
1326  auto whileCtrlOp = rewriter.create<calyx::WhileOp>(loc, cond, symbolAttr);
1327 
1328  /// If a bound was specified, add it.
1329  if (auto bound = whileOp.getBound()) {
1330  // Subtract the number of iterations unrolled into the prologue.
1331  auto prologue = getState<ComponentLoweringState>().getPipelinePrologue(
1332  whileOp.getOperation());
1333  auto unrolledBound = *bound - prologue.size();
1334  whileCtrlOp->setAttr("bound", rewriter.getI64IntegerAttr(unrolledBound));
1335  }
1336 
1337  return whileCtrlOp;
1338  }
1339 };
1340 
1341 /// LateSSAReplacement contains various functions for replacing SSA values that
1342 /// were not replaced during op construction.
1344  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1345 
1346  LogicalResult partiallyLowerFuncToComp(FuncOp funcOp,
1347  PatternRewriter &) const override {
1348  funcOp.walk([&](memref::LoadOp loadOp) {
1349  if (calyx::singleLoadFromMemory(loadOp)) {
1350  /// In buildOpGroups we did not replace loadOp's results, to ensure a
1351  /// link between evaluating groups (which fix the input addresses of a
1352  /// memory op) and a readData result. Now, we may replace these SSA
1353  /// values with their memoryOp readData output.
1354  loadOp.getResult().replaceAllUsesWith(
1355  getState<ComponentLoweringState>()
1356  .getMemoryInterface(loadOp.getMemref())
1357  .readData());
1358  }
1359  });
1360 
1361  return success();
1362  }
1363 };
1364 
1365 /// Erases FuncOp operations.
1367  using FuncOpPartialLoweringPattern::FuncOpPartialLoweringPattern;
1368 
1369  LogicalResult matchAndRewrite(FuncOp funcOp,
1370  PatternRewriter &rewriter) const override {
1371  rewriter.eraseOp(funcOp);
1372  return success();
1373  }
1374 
1375  LogicalResult
1377  PatternRewriter &rewriter) const override {
1378  return success();
1379  }
1380 };
1381 
1382 //===----------------------------------------------------------------------===//
1383 // Pass driver
1384 //===----------------------------------------------------------------------===//
1386  : public LoopScheduleToCalyxBase<LoopScheduleToCalyxPass> {
1387 public:
1390  partialPatternRes(success()) {}
1391  void runOnOperation() override;
1392 
1393  LogicalResult setTopLevelFunction(mlir::ModuleOp moduleOp,
1394  std::string &topLevelFunction) {
1395  if (!topLevelFunctionOpt.empty()) {
1396  if (SymbolTable::lookupSymbolIn(moduleOp, topLevelFunctionOpt) ==
1397  nullptr) {
1398  moduleOp.emitError() << "Top level function '" << topLevelFunctionOpt
1399  << "' not found in module.";
1400  return failure();
1401  }
1402  topLevelFunction = topLevelFunctionOpt;
1403  } else {
1404  /// No top level function set; infer top level if the module only contains
1405  /// a single function, else, throw error.
1406  auto funcOps = moduleOp.getOps<FuncOp>();
1407  if (std::distance(funcOps.begin(), funcOps.end()) == 1)
1408  topLevelFunction = (*funcOps.begin()).getSymName().str();
1409  else {
1410  moduleOp.emitError()
1411  << "Module contains multiple functions, but no top level "
1412  "function was set. Please see --top-level-function";
1413  return failure();
1414  }
1415  }
1416  return success();
1417  }
1418 
1420  enum class Strategy { Once, Greedy };
1421  RewritePatternSet pattern;
1423  };
1424 
1425  //// Labels the entry point of a Calyx program.
1426  /// Furthermore, this function performs validation on the input function,
1427  /// to ensure that we've implemented the capabilities necessary to convert
1428  /// it.
1429  LogicalResult labelEntryPoint(StringRef topLevelFunction) {
1430  // Program legalization - the partial conversion driver will not run
1431  // unless some pattern is provided - provide a dummy pattern.
1432  struct DummyPattern : public OpRewritePattern<mlir::ModuleOp> {
1433  using OpRewritePattern::OpRewritePattern;
1434  LogicalResult matchAndRewrite(mlir::ModuleOp,
1435  PatternRewriter &) const override {
1436  return failure();
1437  }
1438  };
1439 
1440  ConversionTarget target(getContext());
1441  target.addLegalDialect<calyx::CalyxDialect>();
1442  target.addLegalDialect<scf::SCFDialect>();
1443  target.addIllegalDialect<hw::HWDialect>();
1444  target.addIllegalDialect<comb::CombDialect>();
1445 
1446  // For loops should have been lowered to while loops
1447  target.addIllegalOp<scf::ForOp>();
1448 
1449  // Only accept std operations which we've added lowerings for
1450  target.addIllegalDialect<FuncDialect>();
1451  target.addIllegalDialect<ArithDialect>();
1452  target.addLegalOp<AddIOp, SubIOp, CmpIOp, ShLIOp, ShRUIOp, ShRSIOp, AndIOp,
1453  XOrIOp, OrIOp, ExtUIOp, TruncIOp, CondBranchOp, BranchOp,
1454  MulIOp, DivUIOp, DivSIOp, RemUIOp, RemSIOp, ReturnOp,
1455  arith::ConstantOp, IndexCastOp, FuncOp, ExtSIOp>();
1456 
1457  RewritePatternSet legalizePatterns(&getContext());
1458  legalizePatterns.add<DummyPattern>(&getContext());
1459  DenseSet<Operation *> legalizedOps;
1460  if (applyPartialConversion(getOperation(), target,
1461  std::move(legalizePatterns))
1462  .failed())
1463  return failure();
1464 
1465  // Program conversion
1466  return calyx::applyModuleOpConversion(getOperation(), topLevelFunction);
1467  }
1468 
1469  /// 'Once' patterns are expected to take an additional LogicalResult&
1470  /// argument, to forward their result state (greedyPatternRewriteDriver
1471  /// results are skipped for Once patterns).
1472  template <typename TPattern, typename... PatternArgs>
1473  void addOncePattern(SmallVectorImpl<LoweringPattern> &patterns,
1474  PatternArgs &&...args) {
1475  RewritePatternSet ps(&getContext());
1476  ps.add<TPattern>(&getContext(), partialPatternRes, args...);
1477  patterns.push_back(
1478  LoweringPattern{std::move(ps), LoweringPattern::Strategy::Once});
1479  }
1480 
1481  template <typename TPattern, typename... PatternArgs>
1482  void addGreedyPattern(SmallVectorImpl<LoweringPattern> &patterns,
1483  PatternArgs &&...args) {
1484  RewritePatternSet ps(&getContext());
1485  ps.add<TPattern>(&getContext(), args...);
1486  patterns.push_back(
1487  LoweringPattern{std::move(ps), LoweringPattern::Strategy::Greedy});
1488  }
1489 
1490  LogicalResult runPartialPattern(RewritePatternSet &pattern, bool runOnce) {
1491  assert(pattern.getNativePatterns().size() == 1 &&
1492  "Should only apply 1 partial lowering pattern at once");
1493 
1494  // During component creation, the function body is inlined into the
1495  // component body for further processing. However, proper control flow
1496  // will only be established later in the conversion process, so ensure
1497  // that rewriter optimizations (especially DCE) are disabled.
1498  GreedyRewriteConfig config;
1499  config.enableRegionSimplification = false;
1500  if (runOnce)
1501  config.maxIterations = 1;
1502 
1503  /// Can't return applyPatternsAndFoldGreedily. Root isn't
1504  /// necessarily erased so it will always return failed(). Instead,
1505  /// forward the 'succeeded' value from PartialLoweringPatternBase.
1506  (void)applyPatternsAndFoldGreedily(getOperation(), std::move(pattern),
1507  config);
1508  return partialPatternRes;
1509  }
1510 
1511 private:
1512  LogicalResult partialPatternRes;
1513  std::shared_ptr<calyx::CalyxLoweringState> loweringState = nullptr;
1514 };
1515 
1516 void LoopScheduleToCalyxPass::runOnOperation() {
1517  // Clear internal state. See https://github.com/llvm/circt/issues/3235
1518  loweringState.reset();
1519  partialPatternRes = LogicalResult::failure();
1520 
1521  std::string topLevelFunction;
1522  if (failed(setTopLevelFunction(getOperation(), topLevelFunction))) {
1523  signalPassFailure();
1524  return;
1525  }
1526 
1527  /// Start conversion
1528  if (failed(labelEntryPoint(topLevelFunction))) {
1529  signalPassFailure();
1530  return;
1531  }
1532  loweringState = std::make_shared<calyx::CalyxLoweringState>(getOperation(),
1533  topLevelFunction);
1534 
1535  /// --------------------------------------------------------------------------
1536  /// If you are a developer, it may be helpful to add a
1537  /// 'getOperation()->dump()' call after the execution of each stage to
1538  /// view the transformations that's going on.
1539  /// --------------------------------------------------------------------------
1540 
1541  /// A mapping is maintained between a function operation and its corresponding
1542  /// Calyx component.
1543  DenseMap<FuncOp, calyx::ComponentOp> funcMap;
1544  SmallVector<LoweringPattern, 8> loweringPatterns;
1545  calyx::PatternApplicationState patternState;
1546 
1547  /// Creates a new Calyx component for each FuncOp in the inpurt module.
1548  addOncePattern<FuncOpConversion>(loweringPatterns, patternState, funcMap,
1549  *loweringState);
1550 
1551  /// This pattern converts all index typed values to an i32 integer.
1552  addOncePattern<calyx::ConvertIndexTypes>(loweringPatterns, patternState,
1553  funcMap, *loweringState);
1554 
1555  /// This pattern creates registers for all basic-block arguments.
1556  addOncePattern<calyx::BuildBasicBlockRegs>(loweringPatterns, patternState,
1557  funcMap, *loweringState);
1558 
1559  /// This pattern creates registers for the function return values.
1560  addOncePattern<calyx::BuildReturnRegs>(loweringPatterns, patternState,
1561  funcMap, *loweringState);
1562 
1563  /// This pattern creates registers for iteration arguments of scf.while
1564  /// operations. Additionally, creates a group for assigning the initial
1565  /// value of the iteration argument registers.
1566  addOncePattern<BuildWhileGroups>(loweringPatterns, patternState, funcMap,
1567  *loweringState);
1568 
1569  /// This pattern creates registers for all pipeline stages.
1570  addOncePattern<BuildPipelineRegs>(loweringPatterns, patternState, funcMap,
1571  *loweringState);
1572 
1573  /// This pattern converts operations within basic blocks to Calyx library
1574  /// operators. Combinational operations are assigned inside a
1575  /// calyx::CombGroupOp, and sequential inside calyx::GroupOps.
1576  /// Sequential groups are registered with the Block* of which the operation
1577  /// originated from. This is used during control schedule generation. By
1578  /// having a distinct group for each operation, groups are analogous to SSA
1579  /// values in the source program.
1580  addOncePattern<BuildOpGroups>(loweringPatterns, patternState, funcMap,
1581  *loweringState);
1582 
1583  /// This pattern creates groups for all pipeline stages.
1584  addOncePattern<BuildPipelineGroups>(loweringPatterns, patternState, funcMap,
1585  *loweringState);
1586 
1587  /// This pattern traverses the CFG of the program and generates a control
1588  /// schedule based on the calyx::GroupOp's which were registered for each
1589  /// basic block in the source function.
1590  addOncePattern<BuildControl>(loweringPatterns, patternState, funcMap,
1591  *loweringState);
1592 
1593  /// This pass recursively inlines use-def chains of combinational logic (from
1594  /// non-stateful groups) into groups referenced in the control schedule.
1595  addOncePattern<calyx::InlineCombGroups>(loweringPatterns, patternState,
1596  *loweringState);
1597 
1598  /// This pattern performs various SSA replacements that must be done
1599  /// after control generation.
1600  addOncePattern<LateSSAReplacement>(loweringPatterns, patternState, funcMap,
1601  *loweringState);
1602 
1603  /// Eliminate any unused combinational groups. This is done before
1604  /// calyx::RewriteMemoryAccesses to avoid inferring slice components for
1605  /// groups that will be removed.
1606  addGreedyPattern<calyx::EliminateUnusedCombGroups>(loweringPatterns);
1607 
1608  /// This pattern rewrites accesses to memories which are too wide due to
1609  /// index types being converted to a fixed-width integer type.
1610  addOncePattern<calyx::RewriteMemoryAccesses>(loweringPatterns, patternState,
1611  *loweringState);
1612 
1613  /// This pattern removes the source FuncOp which has now been converted into
1614  /// a Calyx component.
1615  addOncePattern<CleanupFuncOps>(loweringPatterns, patternState, funcMap,
1616  *loweringState);
1617 
1618  /// Sequentially apply each lowering pattern.
1619  for (auto &pat : loweringPatterns) {
1620  LogicalResult partialPatternRes = runPartialPattern(
1621  pat.pattern,
1622  /*runOnce=*/pat.strategy == LoweringPattern::Strategy::Once);
1623  if (succeeded(partialPatternRes))
1624  continue;
1625  signalPassFailure();
1626  return;
1627  }
1628 
1629  //===----------------------------------------------------------------------===//
1630  // Cleanup patterns
1631  //===----------------------------------------------------------------------===//
1632  RewritePatternSet cleanupPatterns(&getContext());
1633  cleanupPatterns.add<calyx::MultipleGroupDonePattern,
1634  calyx::NonTerminatingGroupDonePattern>(&getContext());
1635  if (failed(applyPatternsAndFoldGreedily(getOperation(),
1636  std::move(cleanupPatterns)))) {
1637  signalPassFailure();
1638  return;
1639  }
1640 
1641  if (ciderSourceLocationMetadata) {
1642  // Debugging information for the Cider debugger.
1643  // Reference: https://docs.calyxir.org/debug/cider.html
1644  SmallVector<Attribute, 16> sourceLocations;
1645  getOperation()->walk([&](calyx::ComponentOp component) {
1646  return getCiderSourceLocationMetadata(component, sourceLocations);
1647  });
1648 
1649  MLIRContext *context = getOperation()->getContext();
1650  getOperation()->setAttr("calyx.metadata",
1651  ArrayAttr::get(context, sourceLocations));
1652  }
1653 }
1654 
1655 } // namespace pipelinetocalyx
1656 
1657 //===----------------------------------------------------------------------===//
1658 // Pass initialization
1659 //===----------------------------------------------------------------------===//
1660 
1661 std::unique_ptr<OperationPass<ModuleOp>> createLoopScheduleToCalyxPass() {
1662  return std::make_unique<pipelinetocalyx::LoopScheduleToCalyxPass>();
1663 }
1664 
1665 } // namespace circt
assert(baseType &&"element must be base type")
int32_t width
Definition: FIRRTL.cpp:27
@ Input
Definition: HW.h:32
@ Output
Definition: HW.h:32
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: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)
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...
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:16
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
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.