CIRCT 21.0.0git
Loading...
Searching...
No Matches
LowerProcesses.cpp
Go to the documentation of this file.
1//===----------------------------------------------------------------------===//
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
12#include "mlir/Analysis/Liveness.h"
13#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
14#include "mlir/Transforms/RegionUtils.h"
15#include "llvm/Support/Debug.h"
16
17#define DEBUG_TYPE "llhd-lower-processes"
18
19namespace circt {
20namespace llhd {
21#define GEN_PASS_DEF_LOWERPROCESSESPASS
22#include "circt/Dialect/LLHD/Transforms/LLHDPasses.h.inc"
23} // namespace llhd
24} // namespace circt
25
26using namespace mlir;
27using namespace circt;
28using namespace llhd;
29using llvm::SmallDenseSet;
30using llvm::SmallSetVector;
31
32namespace {
33struct Lowering {
34 Lowering(ProcessOp processOp) : processOp(processOp) {}
35 void lower();
36 bool matchControlFlow();
37 void markObservedValues();
38 bool allOperandsObserved();
39 bool isObserved(Value value);
40
41 ProcessOp processOp;
42 WaitOp waitOp;
43 SmallDenseSet<Value> observedValues;
44};
45} // namespace
46
47void Lowering::lower() {
48 // Ensure that the process describes combinational logic.
49 if (!matchControlFlow())
50 return;
51 markObservedValues();
52 if (!allOperandsObserved())
53 return;
54 LLVM_DEBUG(llvm::dbgs() << "Lowering process " << processOp.getLoc() << "\n");
55
56 // Replace the process.
57 OpBuilder builder(processOp);
58 auto executeOp = builder.create<CombinationalOp>(processOp.getLoc(),
59 processOp.getResultTypes());
60 executeOp.getRegion().takeBody(processOp.getBody());
61 processOp.replaceAllUsesWith(executeOp);
62 processOp.erase();
63 processOp = {};
64
65 // Replace the `llhd.wait` with an `llhd.yield`.
66 builder.setInsertionPoint(waitOp);
67 builder.create<YieldOp>(waitOp.getLoc(), waitOp.getYieldOperands());
68 waitOp.erase();
69
70 // Simplify the execute op body region since disconnecting the control flow
71 // loop through the wait op has potentially created unreachable blocks.
72 IRRewriter rewriter(builder);
73 (void)simplifyRegions(rewriter, executeOp->getRegions());
74}
75
76/// Check that the process' entry block trivially joins a control flow loop
77/// immediately after the wait op.
78bool Lowering::matchControlFlow() {
79 // Ensure that there is only a single wait op in the process and that it has
80 // no destination operands.
81 for (auto &block : processOp.getBody()) {
82 if (auto op = dyn_cast<WaitOp>(block.getTerminator())) {
83 if (waitOp) {
84 LLVM_DEBUG(llvm::dbgs() << "Skipping process " << processOp.getLoc()
85 << ": multiple wait ops\n");
86 return false;
87 }
88 waitOp = op;
89 }
90 }
91 if (!waitOp) {
92 LLVM_DEBUG(llvm::dbgs() << "Skipping process " << processOp.getLoc()
93 << ": no wait op\n");
94 return false;
95 }
96 if (!waitOp.getDestOperands().empty()) {
97 LLVM_DEBUG(llvm::dbgs() << "Skipping process " << processOp.getLoc()
98 << ": wait op has destination operands\n");
99 return false;
100 }
101
102 // Helper function to skip across empty blocks with only a single successor.
103 auto skipToMergePoint = [&](Block *block) -> std::pair<Block *, ValueRange> {
104 ValueRange operands;
105 while (auto branchOp = dyn_cast<cf::BranchOp>(block->getTerminator())) {
106 if (!block->without_terminator().empty())
107 break;
108 block = branchOp.getDest();
109 operands = branchOp.getDestOperands();
110 if (std::distance(block->pred_begin(), block->pred_end()) > 1)
111 break;
112 if (!operands.empty())
113 break;
114 }
115 return {block, operands};
116 };
117
118 // Ensure that the entry block and wait op converge on the same block and with
119 // the same block arguments.
120 auto &entry = processOp.getBody().front();
121 auto [entryMergeBlock, entryMergeArgs] = skipToMergePoint(&entry);
122 auto [waitMergeBlock, waitMergeArgs] = skipToMergePoint(waitOp.getDest());
123 if (entryMergeBlock != waitMergeBlock) {
124 LLVM_DEBUG(llvm::dbgs()
125 << "Skipping process " << processOp.getLoc()
126 << ": control from entry and wait does not converge\n");
127 return false;
128 }
129 if (entryMergeArgs != waitMergeArgs) {
130 LLVM_DEBUG(llvm::dbgs() << "Skipping process " << processOp.getLoc()
131 << ": control from entry and wait converges with "
132 "different block arguments\n");
133 return false;
134 }
135
136 // Ensure that no values are live across the wait op.
137 Liveness liveness(processOp);
138 for (auto value : liveness.getLiveOut(waitOp->getBlock())) {
139 if (value.getParentRegion()->isProperAncestor(&processOp.getBody()))
140 continue;
141 LLVM_DEBUG({
142 llvm::dbgs() << "Skipping process " << processOp.getLoc() << ": value ";
143 value.print(llvm::dbgs(), OpPrintingFlags().skipRegions());
144 llvm::dbgs() << " live across wait\n";
145 });
146 return false;
147 }
148
149 return true;
150}
151
152/// Mark values the process observes that are defined outside the process.
153void Lowering::markObservedValues() {
154 SmallVector<Value> worklist;
155 auto markObserved = [&](Value value) {
156 if (observedValues.insert(value).second)
157 worklist.push_back(value);
158 };
159
160 for (auto value : waitOp.getObserved())
161 if (value.getParentRegion()->isProperAncestor(&processOp.getBody()))
162 markObserved(value);
163
164 while (!worklist.empty()) {
165 auto value = worklist.pop_back_val();
166 auto *op = value.getDefiningOp();
167 if (!op)
168 continue;
169
170 // Look through probe ops to mark the probe signal as well, just in case
171 // there may be multiple probes of the same signal.
172 if (auto probeOp = dyn_cast<PrbOp>(op))
173 markObserved(probeOp.getSignal());
174
175 // Look through operations that simply reshape incoming values into an
176 // aggregate form from which any changes remain apparent.
178 hw::BitcastOp>(op))
179 for (auto operand : op->getOperands())
180 markObserved(operand);
181 }
182}
183
184/// Ensure that any value defined outside the process that is used inside the
185/// process is derived entirely from an observed value.
186bool Lowering::allOperandsObserved() {
187 // Collect all ancestor regions such that we can easily check if a value is
188 // defined outside the process.
189 SmallPtrSet<Region *, 4> properAncestors;
190 for (auto *region = processOp->getParentRegion(); region;
191 region = region->getParentRegion())
192 properAncestors.insert(region);
193
194 // Walk all operations under the process and check each operand.
195 auto walkResult = processOp.walk([&](Operation *op) {
196 for (auto operand : op->getOperands()) {
197 // We only care about values defined outside the process.
198 if (!properAncestors.count(operand.getParentRegion()))
199 continue;
200
201 // If the value is observed, all is well.
202 if (isObserved(operand))
203 continue;
204
205 // Otherwise complain and abort.
206 LLVM_DEBUG({
207 llvm::dbgs() << "Skipping process " << processOp.getLoc()
208 << ": unobserved value ";
209 operand.print(llvm::dbgs(), OpPrintingFlags().skipRegions());
210 llvm::dbgs() << "\n";
211 });
212 return WalkResult::interrupt();
213 }
214 return WalkResult::advance();
215 });
216 return !walkResult.wasInterrupted();
217}
218
219/// Check if a value is observed by the wait op, or all its operands are only
220/// derived from observed values.
221bool Lowering::isObserved(Value value) {
222 // Check if the value is trivially observed.
223 if (observedValues.contains(value))
224 return true;
225
226 // Otherwise get the operation that defines it such that we can check if the
227 // value is derived from purely observed values. If it isn't define by an op,
228 // the value is unobserved.
229 auto *defOp = value.getDefiningOp();
230 if (!defOp)
231 return false;
232
233 // Otherwise visit all ops in the fan-in cone and ensure that they are
234 // observed. If any value is unobserved, immediately return false.
235 SmallDenseSet<Operation *> seenOps;
236 SmallVector<Operation *> worklist;
237 seenOps.insert(defOp);
238 worklist.push_back(defOp);
239 while (!worklist.empty()) {
240 auto *op = worklist.pop_back_val();
241
242 // Give up on ops with nested regions.
243 if (op->getNumRegions() != 0)
244 return false;
245
246 // Otherwise check that all operands are observed. If we haven't seen an
247 // operand before, and it is not a signal, add it to the worklist to be
248 // checked.
249 for (auto operand : op->getOperands()) {
250 if (observedValues.contains(operand))
251 continue;
252 if (isa<hw::InOutType>(operand.getType()))
253 return false;
254 auto *defOp = operand.getDefiningOp();
255 if (!defOp || !isMemoryEffectFree(defOp))
256 return false;
257 if (seenOps.insert(defOp).second)
258 worklist.push_back(defOp);
259 }
260 }
261
262 // If we arrive at this point, we weren't able to reach an unobserved value.
263 // Therefore we consider this value derived from only observed values.
264 observedValues.insert(value);
265 return true;
266}
267
268namespace {
269struct LowerProcessesPass
270 : public llhd::impl::LowerProcessesPassBase<LowerProcessesPass> {
271 void runOnOperation() override;
272};
273} // namespace
274
275void LowerProcessesPass::runOnOperation() {
276 SmallVector<ProcessOp> processOps(getOperation().getOps<ProcessOp>());
277 for (auto processOp : processOps)
278 Lowering(processOp).lower();
279}
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.