CIRCT  20.0.0git
Buffers.cpp
Go to the documentation of this file.
1 //===- Buffers.cpp - buffer materialization passes --------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Contains the definitions of buffer materialization passes.
10 //
11 //===----------------------------------------------------------------------===//
12 
16 #include "mlir/IR/PatternMatch.h"
17 #include "mlir/Pass/Pass.h"
18 #include "mlir/Rewrite/FrozenRewritePatternSet.h"
19 #include "mlir/Transforms/DialectConversion.h"
20 
21 namespace circt {
22 namespace handshake {
23 #define GEN_PASS_DEF_HANDSHAKEREMOVEBUFFERS
24 #define GEN_PASS_DEF_HANDSHAKEINSERTBUFFERS
25 #include "circt/Dialect/Handshake/HandshakePasses.h.inc"
26 } // namespace handshake
27 } // namespace circt
28 
29 using namespace circt;
30 using namespace handshake;
31 using namespace mlir;
32 
33 namespace {
34 
35 struct RemoveHandshakeBuffers : public OpRewritePattern<handshake::BufferOp> {
36  using OpRewritePattern::OpRewritePattern;
37 
38  LogicalResult matchAndRewrite(handshake::BufferOp bufferOp,
39  PatternRewriter &rewriter) const override {
40  rewriter.replaceOp(bufferOp, bufferOp.getOperand());
41  return success();
42  }
43 };
44 
45 struct HandshakeRemoveBuffersPass
46  : public circt::handshake::impl::HandshakeRemoveBuffersBase<
47  HandshakeRemoveBuffersPass> {
48  void runOnOperation() override {
49  handshake::FuncOp op = getOperation();
50  ConversionTarget target(getContext());
51  target.addIllegalOp<handshake::BufferOp>();
52  RewritePatternSet patterns(&getContext());
53  patterns.insert<RemoveHandshakeBuffers>(&getContext());
54 
55  if (failed(applyPartialConversion(op, target, std::move(patterns))))
56  signalPassFailure();
57  };
58 };
59 } // namespace
60 // Returns true if a block argument should have buffers added to its uses.
61 static bool shouldBufferArgument(BlockArgument arg) {
62  // At the moment, buffers only make sense on arguments which we know
63  // will lower down to a handshake bundle.
64  return arg.getType().isIntOrFloat() || isa<NoneType>(arg.getType());
65 }
66 
67 static bool isUnbufferedChannel(Operation *definingOp, Operation *usingOp) {
68  return !isa_and_nonnull<BufferOp>(definingOp) && !isa<BufferOp>(usingOp);
69 }
70 
71 static void insertBuffer(Location loc, Value operand, OpBuilder &builder,
72  unsigned numSlots, BufferTypeEnum bufferType) {
73  auto ip = builder.saveInsertionPoint();
74  builder.setInsertionPointAfterValue(operand);
75  auto bufferOp =
76  builder.create<handshake::BufferOp>(loc, operand, numSlots, bufferType);
77  operand.replaceUsesWithIf(
78  bufferOp, function_ref<bool(OpOperand &)>([](OpOperand &operand) -> bool {
79  return !isa<handshake::BufferOp>(operand.getOwner());
80  }));
81  builder.restoreInsertionPoint(ip);
82 }
83 
84 // Inserts buffers at all results of an operation
85 static void bufferResults(OpBuilder &builder, Operation *op, unsigned numSlots,
86  BufferTypeEnum bufferType) {
87  for (auto res : op->getResults()) {
88  Operation *user = *res.getUsers().begin();
89  if (isa<handshake::BufferOp>(user))
90  continue;
91  insertBuffer(op->getLoc(), res, builder, numSlots, bufferType);
92  }
93 }
94 
95 // Add a buffer to any un-buffered channel.
96 static void bufferAllStrategy(Region &r, OpBuilder &builder, unsigned numSlots,
97  BufferTypeEnum bufferType = BufferTypeEnum::seq) {
98 
99  for (auto &arg : r.getArguments()) {
100  if (!shouldBufferArgument(arg))
101  continue;
102  insertBuffer(arg.getLoc(), arg, builder, numSlots, bufferType);
103  }
104 
105  for (auto &defOp : r.getOps()) {
106  for (auto res : defOp.getResults()) {
107  for (auto *useOp : res.getUsers()) {
108  if (!isUnbufferedChannel(&defOp, useOp))
109  continue;
110  insertBuffer(res.getLoc(), res, builder, numSlots, bufferType);
111  }
112  }
113  }
114 }
115 
116 // Returns true if 'src' is within a cycle. 'breaksCycle' is a function which
117 // determines whether an operation breaks a cycle.
118 static bool inCycle(Operation *src,
119  llvm::function_ref<bool(Operation *)> breaksCycle) {
120  SetVector<Operation *> visited;
121  SmallVector<Operation *> stack = {src};
122 
123  while (!stack.empty()) {
124  Operation *curr = stack.pop_back_val();
125 
126  if (visited.contains(curr))
127  continue;
128  visited.insert(curr);
129 
130  if (breaksCycle(curr))
131  continue;
132 
133  for (auto *user : curr->getUsers()) {
134  // If visiting the source node, then we're in a cycle.
135  if (src == user)
136  return true;
137 
138  stack.push_back(user);
139  }
140  }
141  return false;
142 }
143 
144 // Perform a depth first search and insert buffers when cycles are detected.
145 static void
146 bufferCyclesStrategy(Region &r, OpBuilder &builder, unsigned numSlots,
147  BufferTypeEnum /*bufferType*/ = BufferTypeEnum::seq) {
148  // Cycles can only occur at merge-like operations so those are our buffering
149  // targets. Placing the buffer at the output of the merge-like op,
150  // as opposed to naivly placing buffers *whenever* cycles are detected
151  // ensures that we don't place a bunch of buffers on each input of the
152  // merge-like op.
153  auto isSeqBuffer = [](auto op) {
154  auto bufferOp = dyn_cast<handshake::BufferOp>(op);
155  return bufferOp && bufferOp.isSequential();
156  };
157 
158  for (auto mergeOp : r.getOps<MergeLikeOpInterface>()) {
159  // We insert a sequential buffer whenever the op is determined to be
160  // within a cycle (to break combinational cycles). Else, place a FIFO
161  // buffer.
162  bool sequential = inCycle(mergeOp, isSeqBuffer);
163  bufferResults(builder, mergeOp, numSlots,
164  sequential ? BufferTypeEnum::seq : BufferTypeEnum::fifo);
165  }
166 }
167 
168 // Combination of bufferCyclesStrategy and bufferAllStrategy, where we add a
169 // sequential buffer on graph cycles, and add FIFO buffers on all other
170 // connections.
171 static void bufferAllFIFOStrategy(Region &r, OpBuilder &builder,
172  unsigned numSlots) {
173  // First, buffer cycles with sequential buffers
174  bufferCyclesStrategy(r, builder, /*numSlots=*/numSlots,
175  /*bufferType=*/BufferTypeEnum::seq);
176  // Then, buffer remaining channels with transparent FIFO buffers
177  bufferAllStrategy(r, builder, numSlots,
178  /*bufferType=*/BufferTypeEnum::fifo);
179 }
180 
181 static LogicalResult bufferRegion(Region &r, OpBuilder &builder,
182  StringRef strategy, unsigned bufferSize) {
183  if (strategy == "cycles")
184  bufferCyclesStrategy(r, builder, bufferSize);
185  else if (strategy == "all")
186  bufferAllStrategy(r, builder, bufferSize);
187  else if (strategy == "allFIFO")
188  bufferAllFIFOStrategy(r, builder, bufferSize);
189  else
190  return r.getParentOp()->emitOpError()
191  << "Unknown buffer strategy: " << strategy;
192 
193  return success();
194 }
195 
196 namespace {
197 struct HandshakeInsertBuffersPass
198  : public circt::handshake::impl::HandshakeInsertBuffersBase<
199  HandshakeInsertBuffersPass> {
200  HandshakeInsertBuffersPass(const std::string &strategy, unsigned bufferSize) {
201  this->strategy = strategy;
202  this->bufferSize = bufferSize;
203  }
204 
205  void runOnOperation() override {
206  auto f = getOperation();
207  if (f.isExternal())
208  return;
209 
210  OpBuilder builder(f.getContext());
211 
212  if (failed(bufferRegion(f.getBody(), builder, strategy, bufferSize)))
213  signalPassFailure();
214  }
215 };
216 
217 } // namespace
218 
219 std::unique_ptr<mlir::Pass>
221  return std::make_unique<HandshakeRemoveBuffersPass>();
222 }
223 
224 std::unique_ptr<mlir::OperationPass<handshake::FuncOp>>
226  unsigned bufferSize) {
227  return std::make_unique<HandshakeInsertBuffersPass>(strategy, bufferSize);
228 }
static void bufferResults(OpBuilder &builder, Operation *op, unsigned numSlots, BufferTypeEnum bufferType)
Definition: Buffers.cpp:85
static void bufferAllFIFOStrategy(Region &r, OpBuilder &builder, unsigned numSlots)
Definition: Buffers.cpp:171
static bool isUnbufferedChannel(Operation *definingOp, Operation *usingOp)
Definition: Buffers.cpp:67
static void insertBuffer(Location loc, Value operand, OpBuilder &builder, unsigned numSlots, BufferTypeEnum bufferType)
Definition: Buffers.cpp:71
static void bufferAllStrategy(Region &r, OpBuilder &builder, unsigned numSlots, BufferTypeEnum bufferType=BufferTypeEnum::seq)
Definition: Buffers.cpp:96
static LogicalResult bufferRegion(Region &r, OpBuilder &builder, StringRef strategy, unsigned bufferSize)
Definition: Buffers.cpp:181
static void bufferCyclesStrategy(Region &r, OpBuilder &builder, unsigned numSlots, BufferTypeEnum=BufferTypeEnum::seq)
Definition: Buffers.cpp:146
static bool shouldBufferArgument(BlockArgument arg)
Definition: Buffers.cpp:61
static bool inCycle(Operation *src, llvm::function_ref< bool(Operation *)> breaksCycle)
Definition: Buffers.cpp:118
Strategy strategy
std::unique_ptr< mlir::OperationPass< handshake::FuncOp > > createHandshakeInsertBuffersPass(const std::string &strategy="all", unsigned bufferSize=2)
Definition: Buffers.cpp:225
std::unique_ptr< mlir::Pass > createHandshakeRemoveBuffersPass()
Definition: Buffers.cpp:220
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21