CIRCT  18.0.0git
CFToHandshake.h
Go to the documentation of this file.
1 //===- CFToHandshake.h ------------------------------------------*- 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 // This file declares passes which together will lower the Standard dialect to
10 // Handshake dialect.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef CIRCT_CONVERSION_CFTOHANDSHAKE_H_
15 #define CIRCT_CONVERSION_CFTOHANDSHAKE_H_
16 
21 #include "mlir/Transforms/DialectConversion.h"
22 
23 #include <memory>
24 
25 namespace mlir {
26 class ModuleOp;
27 template <typename T>
29 } // namespace mlir
30 
31 namespace circt {
32 namespace handshake {
33 
34 // ============================================================================
35 // Partial lowering infrastructure
36 // ============================================================================
37 
39  llvm::function_ref<LogicalResult(Region &, ConversionPatternRewriter &)>;
40 // Convenience function for executing a PartialLowerRegion with a provided
41 // partial lowering function.
42 LogicalResult partiallyLowerRegion(const RegionLoweringFunc &loweringFunc,
43  MLIRContext *ctx, Region &r);
44 
45 // Holds the shared state of the different transformations required to transform
46 // Standard to Handshake operations. The transformations are expressed as member
47 // functions to simplify access to the state.
48 //
49 // This class' member functions expect a rewriter that matched on the parent
50 // operation of the encapsulated region.
52 public:
53  struct MergeOpInfo {
54  Operation *op;
55  Value val;
56  SmallVector<Backedge> dataEdges;
57  std::optional<Backedge> indexEdge{};
58  };
59 
60  using BlockValues = DenseMap<Block *, std::vector<Value>>;
61  using BlockOps = DenseMap<Block *, std::vector<MergeOpInfo>>;
62  using ValueMap = DenseMap<Value, Value>;
64  llvm::MapVector<Value, std::vector<Operation *>>;
65 
66  explicit HandshakeLowering(Region &r) : r(r) {}
67 
68  LogicalResult addMergeOps(ConversionPatternRewriter &rewriter);
69  LogicalResult addBranchOps(ConversionPatternRewriter &rewriter);
70  LogicalResult replaceCallOps(ConversionPatternRewriter &rewriter);
71 
72  template <typename TSrcTerm, typename TDstTerm>
73  LogicalResult setControlOnlyPath(ConversionPatternRewriter &rewriter,
74  Value entryCtrl) {
75  assert(entryCtrl.getType().isa<NoneType>() &&
76  "Expected NoneType for entry control value");
77  // Creates start and end points of the control-only path
78  Block *entryBlock = &r.front();
79  setBlockEntryControl(entryBlock, entryCtrl);
80 
81  // Replace original return ops with new returns with additional control
82  // input
83  for (auto retOp : llvm::make_early_inc_range(r.getOps<TSrcTerm>())) {
84  rewriter.setInsertionPoint(retOp);
85  SmallVector<Value, 8> operands(retOp->getOperands());
86  operands.push_back(entryCtrl);
87  rewriter.replaceOpWithNewOp<TDstTerm>(retOp, operands);
88  }
89 
90  // Store the number of block arguments in each block
91  DenseMap<Block *, unsigned> numArgsPerBlock;
92  for (auto &block : r.getBlocks())
93  numArgsPerBlock[&block] = block.getNumArguments();
94 
95  // Apply SSA maximization on the newly added entry block argument to
96  // propagate it explicitly between the start-point of the control-only
97  // network and the function's terminators
98  if (failed(maximizeSSA(entryCtrl, rewriter)))
99  return failure();
100 
101  // Identify all block arguments belonging to the control-only network
102  // (needed to later insert control merges after those values). These are the
103  // last arguments to blocks that got a new argument during SSA maximization
104  for (auto &[block, numArgs] : numArgsPerBlock)
105  if (block->getNumArguments() != numArgs)
106  setBlockEntryControl(block, block->getArguments().back());
107 
108  return success();
109  }
110 
111  LogicalResult connectConstantsToControl(ConversionPatternRewriter &rewriter,
112  bool sourceConstants);
113 
114  LogicalResult feedForwardRewriting(ConversionPatternRewriter &rewriter);
115  LogicalResult loopNetworkRewriting(ConversionPatternRewriter &rewriter);
116 
117  BlockOps insertMergeOps(ValueMap &mergePairs, BackedgeBuilder &edgeBuilder,
118  ConversionPatternRewriter &rewriter);
119 
120  // Insert appropriate type of Merge CMerge for control-only path,
121  // Merge for single-successor blocks, Mux otherwise
122  MergeOpInfo insertMerge(Block *block, Value val, BackedgeBuilder &edgeBuilder,
123  ConversionPatternRewriter &rewriter);
124 
125  // Replaces standard memory ops with their handshake version (i.e.,
126  // ops which connect to memory/LSQ). Returns a map with an ordered
127  // list of new ops corresponding to each memref. Later, we instantiate
128  // a memory node for each memref and connect it to its load/store ops
129  LogicalResult replaceMemoryOps(ConversionPatternRewriter &rewriter,
130  MemRefToMemoryAccessOp &memRefOps);
131 
132  LogicalResult connectToMemory(ConversionPatternRewriter &rewriter,
133  MemRefToMemoryAccessOp memRefOps, bool lsq);
134  void setMemOpControlInputs(ConversionPatternRewriter &rewriter,
135  ArrayRef<Operation *> memOps, Operation *memOp,
136  int offset, ArrayRef<int> cntrlInd);
137 
138  // Returns the entry control value for operations contained within this
139  // block.
140  Value getBlockEntryControl(Block *block) const;
141 
142  void setBlockEntryControl(Block *block, Value v);
143 
144  Region &getRegion() { return r; }
145  MLIRContext *getContext() { return r.getContext(); }
146 
147 protected:
148  Region &r;
149 
150  /// Start point of the control-only network
151  BlockArgument startCtrl;
152 
153 private:
154  DenseMap<Block *, Value> blockEntryControlMap;
155 };
156 
157 // Driver for the HandshakeLowering class.
158 // Note: using two different vararg template names due to potantial references
159 // that would cause a type mismatch
160 template <typename T, typename... TArgs, typename... TArgs2>
161 LogicalResult runPartialLowering(
162  T &instance,
163  LogicalResult (T::*memberFunc)(ConversionPatternRewriter &, TArgs2...),
164  TArgs &...args) {
165  return partiallyLowerRegion(
166  [&](Region &, ConversionPatternRewriter &rewriter) -> LogicalResult {
167  return (instance.*memberFunc)(rewriter, args...);
168  },
169  instance.getContext(), instance.getRegion());
170 }
171 
172 /// Remove basic blocks inside the given region. This allows the result to be
173 /// a valid graph region, since multi-basic block regions are not allowed to
174 /// be graph regions currently.
175 void removeBasicBlocks(Region &r);
176 
177 // Helper to check the validity of the dataflow conversion
178 // Driver that applies the partial lowerings expressed in HandshakeLowering to
179 // the region encapsulated in it. The region is assumed to have a terminator of
180 // type TSrcTerm, and will replace it with TDstTerm. See HandshakeLowering for
181 // the different lowering steps.
182 template <typename TSrcTerm, typename TDstTerm>
183 LogicalResult lowerRegion(HandshakeLowering &hl, bool sourceConstants,
184  bool disableTaskPipelining, Value entryCtrl) {
185  // Perform initial dataflow conversion. This process allows for the use of
186  // non-deterministic merge-like operations.
188 
189  if (failed(
191  return failure();
192  if (failed(runPartialLowering(
193  hl, &HandshakeLowering::setControlOnlyPath<TSrcTerm, TDstTerm>,
194  entryCtrl)))
195  return failure();
197  return failure();
199  return failure();
201  return failure();
202 
203  // The following passes modifies the dataflow graph to being safe for task
204  // pipelining. In doing so, non-deterministic merge structures are replaced
205  // for deterministic structures.
206  if (!disableTaskPipelining) {
207  if (failed(
209  return failure();
210  if (failed(
212  return failure();
213  }
214 
215  if (failed(runPartialLowering(
216  hl, &HandshakeLowering::connectConstantsToControl, sourceConstants)))
217  return failure();
218 
219  bool lsq = false;
221  lsq)))
222  return failure();
223 
224  // Legalize the resulting regions, removing basic blocks and performing
225  // any simple conversions.
227 
228  return success();
229 }
230 
231 /// Lowers the mlir operations into handshake that are not part of the dataflow
232 /// conversion.
233 LogicalResult postDataflowConvert(Operation *op);
234 
235 } // namespace handshake
236 
237 std::unique_ptr<mlir::OperationPass<mlir::ModuleOp>>
239 
240 std::unique_ptr<mlir::OperationPass<mlir::ModuleOp>>
241 createCFToHandshakePass(bool sourceConstants = false,
242  bool disableTaskPipelining = false);
243 
244 std::unique_ptr<mlir::OperationPass<handshake::FuncOp>>
246 
247 std::unique_ptr<mlir::OperationPass<handshake::FuncOp>>
249 
250 /// Insert additional blocks that serve as counterparts to the blocks that
251 /// diverged the control flow.
252 /// The resulting merge block tree is guaranteed to be a binary tree.
253 ///
254 /// This transformation does treat loops like a single block and thus does not
255 /// affect them.
256 mlir::LogicalResult
257 insertMergeBlocks(mlir::Region &r, mlir::ConversionPatternRewriter &rewriter);
258 
259 std::unique_ptr<mlir::Pass> createInsertMergeBlocksPass();
260 
261 } // namespace circt
262 
263 #endif // CIRCT_CONVERSION_CFTOHANDSHAKE_H_
assert(baseType &&"element must be base type")
Instantiate one of these and use it to build typed backedges.
BlockOps insertMergeOps(ValueMap &mergePairs, BackedgeBuilder &edgeBuilder, ConversionPatternRewriter &rewriter)
MergeOpInfo insertMerge(Block *block, Value val, BackedgeBuilder &edgeBuilder, ConversionPatternRewriter &rewriter)
LogicalResult loopNetworkRewriting(ConversionPatternRewriter &rewriter)
BlockArgument startCtrl
Start point of the control-only network.
DenseMap< Block *, std::vector< MergeOpInfo > > BlockOps
Definition: CFToHandshake.h:61
LogicalResult feedForwardRewriting(ConversionPatternRewriter &rewriter)
LogicalResult replaceCallOps(ConversionPatternRewriter &rewriter)
void setMemOpControlInputs(ConversionPatternRewriter &rewriter, ArrayRef< Operation * > memOps, Operation *memOp, int offset, ArrayRef< int > cntrlInd)
LogicalResult addMergeOps(ConversionPatternRewriter &rewriter)
LogicalResult replaceMemoryOps(ConversionPatternRewriter &rewriter, MemRefToMemoryAccessOp &memRefOps)
DenseMap< Block *, std::vector< Value > > BlockValues
Definition: CFToHandshake.h:60
LogicalResult connectConstantsToControl(ConversionPatternRewriter &rewriter, bool sourceConstants)
llvm::MapVector< Value, std::vector< Operation * > > MemRefToMemoryAccessOp
Definition: CFToHandshake.h:64
DenseMap< Block *, Value > blockEntryControlMap
LogicalResult setControlOnlyPath(ConversionPatternRewriter &rewriter, Value entryCtrl)
Definition: CFToHandshake.h:73
DenseMap< Value, Value > ValueMap
Definition: CFToHandshake.h:62
Value getBlockEntryControl(Block *block) const
void setBlockEntryControl(Block *block, Value v)
LogicalResult connectToMemory(ConversionPatternRewriter &rewriter, MemRefToMemoryAccessOp memRefOps, bool lsq)
LogicalResult addBranchOps(ConversionPatternRewriter &rewriter)
LogicalResult runPartialLowering(T &instance, LogicalResult(T::*memberFunc)(ConversionPatternRewriter &, TArgs2...), TArgs &...args)
LogicalResult postDataflowConvert(Operation *op)
Lowers the mlir operations into handshake that are not part of the dataflow conversion.
LogicalResult lowerRegion(HandshakeLowering &hl, bool sourceConstants, bool disableTaskPipelining, Value entryCtrl)
llvm::function_ref< LogicalResult(Region &, ConversionPatternRewriter &)> RegionLoweringFunc
Definition: CFToHandshake.h:39
void removeBasicBlocks(Region &r)
Remove basic blocks inside the given region.
LogicalResult partiallyLowerRegion(const RegionLoweringFunc &loweringFunc, MLIRContext *ctx, Region &r)
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21
std::unique_ptr< mlir::Pass > createInsertMergeBlocksPass()
mlir::LogicalResult insertMergeBlocks(mlir::Region &r, mlir::ConversionPatternRewriter &rewriter)
Insert additional blocks that serve as counterparts to the blocks that diverged the control flow.
LogicalResult maximizeSSA(Value value, PatternRewriter &rewriter)
Converts a single value within a function into maximal SSA form.
Definition: MaximizeSSA.cpp:81
std::unique_ptr< mlir::OperationPass< mlir::ModuleOp > > createCFToHandshakePass(bool sourceConstants=false, bool disableTaskPipelining=false)
std::unique_ptr< mlir::OperationPass< mlir::ModuleOp > > createHandshakeAnalysisPass()
std::unique_ptr< mlir::OperationPass< handshake::FuncOp > > createHandshakeRemoveBlockPass()
std::unique_ptr< mlir::OperationPass< handshake::FuncOp > > createHandshakeCanonicalizePass()