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