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