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  insertFork(barg, rewriter);
111 
112  return success();
113 }
114 
115 // Create sink for every unused result
116 static LogicalResult addSinkOps(Block &block, OpBuilder &rewriter) {
117  for (auto arg : block.getArguments()) {
118  if (isDCTyped(arg) && arg.use_empty())
119  insertSink(arg, rewriter);
120  }
121 
122  // Materialization adds operations _after_ their definition, so we can't use
123  // llvm::make_early_inc_range. Copy over all of the ops to process.
124  llvm::SmallVector<Operation *> opsToProcess;
125  for (auto &op : block.getOperations())
126  opsToProcess.push_back(&op);
127 
128  for (Operation *op : opsToProcess) {
129  if (op->getNumResults() == 0)
130  continue;
131 
132  for (auto result : op->getResults()) {
133  if (isDCTyped(result) && result.use_empty())
134  insertSink(result, rewriter);
135  }
136  }
137 
138  return success();
139 }
140 
141 namespace {
142 struct DCMaterializeForksSinksPass
143  : public circt::dc::impl::DCMaterializeForksSinksBase<
144  DCMaterializeForksSinksPass> {
145  void runOnOperation() override {
146  auto *op = getOperation();
147  OpBuilder builder(op);
148 
149  auto walkRes = op->walk([&](mlir::Block *block) {
150  if (addForkOps(*block, builder).failed() ||
151  addSinkOps(*block, builder).failed())
152  return WalkResult::interrupt();
153 
154  return WalkResult::advance();
155  });
156 
157  if (walkRes.wasInterrupted())
158  return signalPassFailure();
159  };
160 };
161 
162 struct DCDematerializeForksSinksPass
163  : public circt::dc::impl::DCDematerializeForksSinksBase<
164  DCDematerializeForksSinksPass> {
165  void runOnOperation() override {
166  auto *op = getOperation();
167  op->walk([&](dc::SinkOp sinkOp) { sinkOp.erase(); });
168  op->walk([&](dc::ForkOp forkOp) {
169  for (auto res : forkOp->getResults())
170  res.replaceAllUsesWith(forkOp.getOperand());
171  forkOp.erase();
172  });
173  };
174 };
175 
176 } // namespace
177 
178 std::unique_ptr<mlir::Pass> circt::dc::createDCMaterializeForksSinksPass() {
179  return std::make_unique<DCMaterializeForksSinksPass>();
180 }
181 
182 std::unique_ptr<mlir::Pass> circt::dc::createDCDematerializeForksSinksPass() {
183  return std::make_unique<DCDematerializeForksSinksPass>();
184 }
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