CIRCT  20.0.0git
DCMaterialization.cpp
Go to the documentation of this file.
1 //===- DCMaterialization.cpp - Fork/sink materialization pass ---*- 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 the Fork/sink materialization pass.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "circt/Dialect/DC/DCOps.h"
15 #include "mlir/Pass/Pass.h"
16 
17 namespace circt {
18 namespace dc {
19 #define GEN_PASS_DEF_DCMATERIALIZEFORKSSINKS
20 #define GEN_PASS_DEF_DCDEMATERIALIZEFORKSSINKS
21 #include "circt/Dialect/DC/DCPasses.h.inc"
22 } // namespace dc
23 } // namespace circt
24 
25 using namespace circt;
26 using namespace dc;
27 using namespace mlir;
28 
29 static bool isDCTyped(Value v) {
30  return isa<dc::TokenType, dc::ValueType>(v.getType());
31 }
32 
33 static void replaceFirstUse(Operation *op, Value oldVal, Value newVal) {
34  for (int i = 0, e = op->getNumOperands(); i < e; ++i)
35  if (op->getOperand(i) == oldVal) {
36  op->setOperand(i, newVal);
37  break;
38  }
39 }
40 
41 // Adds a sink to the provided token or value-typed Value `v`.
42 static void insertSink(Value v, OpBuilder &rewriter) {
43  rewriter.setInsertionPointAfterValue(v);
44  if (isa<ValueType>(v.getType())) {
45  // Unpack before sinking
46  v = rewriter.create<UnpackOp>(v.getLoc(), v).getToken();
47  }
48 
49  rewriter.create<SinkOp>(v.getLoc(), v);
50 }
51 
52 // Adds a fork of the provided token or value-typed Value `result`.
53 static void insertFork(Value result, OpBuilder &rewriter) {
54  rewriter.setInsertionPointAfterValue(result);
55  // Get successor operations
56  std::vector<Operation *> opsToProcess;
57  for (auto &u : result.getUses())
58  opsToProcess.push_back(u.getOwner());
59 
60  bool isValue = isa<ValueType>(result.getType());
61  Value token = result;
62  Value value;
63  if (isValue) {
64  auto unpack = rewriter.create<UnpackOp>(result.getLoc(), result);
65  token = unpack.getToken();
66  value = unpack.getOutput();
67  }
68 
69  // Insert fork after op
70  auto forkSize = opsToProcess.size();
71  auto newFork = rewriter.create<ForkOp>(token.getLoc(), token, forkSize);
72 
73  // Modify operands of successor
74  // opsToProcess may have multiple instances of same operand
75  // Replace uses one by one to assign different fork outputs to them
76  for (auto [op, forkOutput] : llvm::zip(opsToProcess, newFork->getResults())) {
77  Value forkRes = forkOutput;
78  if (isValue)
79  forkRes =
80  rewriter.create<PackOp>(forkRes.getLoc(), forkRes, value).getOutput();
81  replaceFirstUse(op, result, forkRes);
82  }
83 }
84 
85 // Insert Fork Operation for every operation and function argument with more
86 // than one successor.
87 static LogicalResult addForkOps(Block &block, OpBuilder &rewriter) {
88  // Materialization adds operations _after_ their definition, so we can't use
89  // llvm::make_early_inc_range. Copy over all of the ops to process.
90  llvm::SmallVector<Operation *> opsToProcess;
91  for (auto &op : block.getOperations())
92  opsToProcess.push_back(&op);
93 
94  for (Operation *op : opsToProcess) {
95  // Ignore terminators.
96  if (!op->hasTrait<OpTrait::IsTerminator>()) {
97  for (auto result : op->getResults()) {
98  if (!isDCTyped(result))
99  continue;
100  // If there is a result, it is used more than once, and it is a DC
101  // type, fork it!
102  if (!result.use_empty() && !result.hasOneUse())
103  insertFork(result, rewriter);
104  }
105  }
106  }
107 
108  for (auto barg : block.getArguments())
109  if (!barg.use_empty() && !barg.hasOneUse())
110  if (isDCTyped(barg))
111  insertFork(barg, rewriter);
112 
113  return success();
114 }
115 
116 // Create sink for every unused result
117 static LogicalResult addSinkOps(Block &block, OpBuilder &rewriter) {
118  for (auto arg : block.getArguments()) {
119  if (isDCTyped(arg) && arg.use_empty())
120  insertSink(arg, rewriter);
121  }
122 
123  // Materialization adds operations _after_ their definition, so we can't use
124  // llvm::make_early_inc_range. Copy over all of the ops to process.
125  llvm::SmallVector<Operation *> opsToProcess;
126  for (auto &op : block.getOperations())
127  opsToProcess.push_back(&op);
128 
129  for (Operation *op : opsToProcess) {
130  if (op->getNumResults() == 0)
131  continue;
132 
133  for (auto result : op->getResults()) {
134  if (isDCTyped(result) && result.use_empty())
135  insertSink(result, rewriter);
136  }
137  }
138 
139  return success();
140 }
141 
142 namespace {
143 struct DCMaterializeForksSinksPass
144  : public circt::dc::impl::DCMaterializeForksSinksBase<
145  DCMaterializeForksSinksPass> {
146  void runOnOperation() override {
147  auto *op = getOperation();
148  OpBuilder builder(op);
149 
150  auto walkRes = op->walk([&](mlir::Block *block) {
151  if (addForkOps(*block, builder).failed() ||
152  addSinkOps(*block, builder).failed())
153  return WalkResult::interrupt();
154 
155  return WalkResult::advance();
156  });
157 
158  if (walkRes.wasInterrupted())
159  return signalPassFailure();
160  };
161 };
162 
163 struct DCDematerializeForksSinksPass
164  : public circt::dc::impl::DCDematerializeForksSinksBase<
165  DCDematerializeForksSinksPass> {
166  void runOnOperation() override {
167  auto *op = getOperation();
168  op->walk([&](dc::SinkOp sinkOp) { sinkOp.erase(); });
169  op->walk([&](dc::ForkOp forkOp) {
170  for (auto res : forkOp->getResults())
171  res.replaceAllUsesWith(forkOp.getOperand());
172  forkOp.erase();
173  });
174  };
175 };
176 
177 } // namespace
178 
179 std::unique_ptr<mlir::Pass> circt::dc::createDCMaterializeForksSinksPass() {
180  return std::make_unique<DCMaterializeForksSinksPass>();
181 }
182 
183 std::unique_ptr<mlir::Pass> circt::dc::createDCDematerializeForksSinksPass() {
184  return std::make_unique<DCDematerializeForksSinksPass>();
185 }
static LogicalResult addSinkOps(Block &block, OpBuilder &rewriter)
static void insertSink(Value v, OpBuilder &rewriter)
static void insertFork(Value result, OpBuilder &rewriter)
static bool isDCTyped(Value v)
static LogicalResult addForkOps(Block &block, OpBuilder &rewriter)
static void replaceFirstUse(Operation *op, Value oldVal, Value newVal)
std::unique_ptr< mlir::Pass > createDCDematerializeForksSinksPass()
std::unique_ptr< mlir::Pass > createDCMaterializeForksSinksPass()
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21