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