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