CIRCT  19.0.0git
ProbeDCE.cpp
Go to the documentation of this file.
1 //===- ProbeDCE.cpp - Delete input probes and dead dead probe ops ---------===//
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 defines the ProbeDCE pass. This pass ensures all input probes
10 // are removed and diagnoses where that is not possible.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "PassDetails.h"
19 #include "mlir/IR/ImplicitLocOpBuilder.h"
20 #include "mlir/IR/Iterators.h"
21 #include "mlir/IR/Threading.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/SaveAndRestore.h"
24 
25 #define DEBUG_TYPE "firrtl-probe-dce"
26 
27 using namespace circt;
28 using namespace firrtl;
29 
30 //===----------------------------------------------------------------------===//
31 // Pass Infrastructure
32 //===----------------------------------------------------------------------===//
33 
34 namespace {
35 struct ProbeDCEPass : public ProbeDCEBase<ProbeDCEPass> {
36  using ProbeDCEBase::ProbeDCEBase;
37  void runOnOperation() override;
38 
39  /// Process the specified module, instance graph only used to
40  /// keep it up-to-date if specified.
41  /// Returns true if changes were made (or reports failure).
43  process(FModuleLike mod,
44  std::optional<std::reference_wrapper<InstanceGraph>> ig);
45 };
46 } // end anonymous namespace
47 
48 void ProbeDCEPass::runOnOperation() {
49  LLVM_DEBUG(llvm::dbgs()
50  << "===- Running ProbeDCE Pass "
51  "--------------------------------------------------===\n");
52 
53  SmallVector<Operation *, 0> ops(getOperation().getOps<FModuleLike>());
54 
55  auto ig = getCachedAnalysis<InstanceGraph>();
56 
57  std::atomic<bool> anyChanges(false);
58  auto result = failableParallelForEach(&getContext(), ops, [&](Operation *op) {
59  auto failOrChanged = process(cast<FModuleLike>(op), ig);
60  if (failed(failOrChanged))
61  return failure();
62  auto changed = *failOrChanged;
63  if (changed)
64  anyChanges = true;
65  return success();
66  });
67 
68  if (result.failed())
69  signalPassFailure();
70 
71  if (ig)
72  markAnalysesPreserved<InstanceGraph>();
73  if (!anyChanges)
74  markAllAnalysesPreserved();
75 }
76 
77 /// This is the pass constructor.
78 std::unique_ptr<mlir::Pass> circt::firrtl::createProbeDCEPass() {
79  return std::make_unique<ProbeDCEPass>();
80 }
81 
82 //===----------------------------------------------------------------------===//
83 // Per-module input probe removal.
84 //===----------------------------------------------------------------------===//
85 
86 /// Forward slice of input probes.
88  // Build cumulatively, slice individually for diagnostic specificity.
89  DenseSet<Operation *> slice;
90 
91  // Current slice source, only valid while slicing.
92  BlockArgument currentSliceSource;
93 
94  /// Operation is in forward slice, add.
95  void chase(SmallVectorImpl<Operation *> &worklist, Operation *op) {
96  if (!slice.insert(op).second)
97  return;
98  worklist.push_back(op);
99  }
100 
101  /// Forward slice through value -> users.
102  void chaseUsers(SmallVectorImpl<Operation *> &worklist, Value v) {
103  for (auto *user : v.getUsers())
104  chase(worklist, user);
105  }
106 
107  /// Upwards chase for connect, and chase all users.
108  LogicalResult chaseVal(SmallVectorImpl<Operation *> &worklist, Value v) {
109  if (auto depArg = dyn_cast<BlockArgument>(v)) {
110  // Input probe flows to different argument?
111  // With current (valid) IR this should not be possible.
112  if (depArg != currentSliceSource)
113  return emitError(depArg.getLoc(), "argument depends on input probe")
114  .attachNote(currentSliceSource.getLoc())
115  << "input probe";
116  // Shouldn't happen either, but safe to ignore.
117  return success();
118  }
119  auto *op = v.getDefiningOp();
120  assert(op);
121  chase(worklist, op);
122  chaseUsers(worklist, v);
123  return success();
124  }
125 
126 public:
127  bool contains(Operation *op) const { return slice.contains(op); }
128  bool empty() const { return slice.empty(); }
129  size_t size() const { return slice.size(); }
130 
131  const DenseSet<Operation *> &get() const { return slice; }
132 
133  /// Forward slice through the given input probe argument, diagnosing
134  /// illegal/unsupported uses if encountered.
135  LogicalResult add(BlockArgument arg) {
136  // Set current slice source for use by helpers, clear when done.
137  llvm::SaveAndRestore<BlockArgument> x(this->currentSliceSource, arg);
138  // Slice worklist.
139  SmallVector<Operation *> worklist;
140 
141  // Start with all users of the input probe.
142  chaseUsers(worklist, arg);
143 
144  while (!worklist.empty()) {
145  auto *op = worklist.pop_back_val();
146 
147  // Generally just walk users. Only "backwards" chasing is for connect,
148  // which only flows to the destination which must not be a refsub or cast.
149  auto result =
150  TypeSwitch<Operation *, LogicalResult>(op)
151  .Case([&](InstanceOp inst) {
152  // Ignore, only reachable via connect which also chases users
153  // for us. Don't chase results not in slice.
154  return success();
155  })
156  .Case([&](FConnectLike connect) {
157  return chaseVal(worklist, connect.getDest());
158  })
159  .Case([&](RefSubOp op) {
160  chaseUsers(worklist, op.getResult());
161  return success();
162  })
163  .Case([&](RefCastOp op) {
164  chaseUsers(worklist, op.getResult());
165  return success();
166  })
167  .Case([&](WireOp op) {
168  // Ignore, only reachable via connect which also chases users
169  // for us.
170  return success();
171  })
172  .Default([&](auto *op) -> LogicalResult {
173  return emitError(op->getLoc(), "input probes cannot be used")
174  .attachNote(arg.getLoc())
175  << "input probe here";
176  });
177  if (failed(result))
178  return result;
179  }
180  return success();
181  }
182 };
183 
185 ProbeDCEPass::process(FModuleLike mod,
186  std::optional<std::reference_wrapper<InstanceGraph>> ig) {
187  SmallVector<size_t> probePortIndices;
188 
189  // Find input probes.
190  for (auto idx : llvm::seq(mod.getNumPorts())) {
191  if (mod.getPortDirection(idx) == Direction::In &&
192  type_isa<RefType>(mod.getPortType(idx)))
193  probePortIndices.push_back(idx);
194  }
195 
196  // Reject input probes across boundaries.
197  if (!probePortIndices.empty() && mod.isPublic()) {
198  auto idx = probePortIndices.front();
199  return mlir::emitError(mod.getPortLocation(idx),
200  "input probe not allowed on public module");
201  }
202  auto modOp = dyn_cast<FModuleOp>(mod.getOperation());
203  if (!modOp) {
204  if (!probePortIndices.empty()) {
205  auto idx = probePortIndices.front();
206  return mlir::emitError(mod.getPortLocation(idx),
207  "input probe not allowed on this module kind");
208  }
209  // No changes made.
210  return false;
211  }
212 
213  BitVector portsToErase(mod.getNumPorts());
214 
215  // Forward slice over users of each.
216  // Build cumulatively, slice individually for diagnostic specificity.
218  for (auto idx : probePortIndices) {
219  portsToErase.set(idx);
220  if (failed(slice.add(modOp.getArgument(idx))))
221  return failure();
222  }
223 
224  // Track whether any changes were made.
225  bool changes = portsToErase.any();
226 
227  // Walk the module, removing all operations in forward slice from input probes
228  // and updating all instances to reflect no more input probes anywhere.
229  // Walk post-order, reverse, so can erase as we encounter operations.
230  modOp.walk<mlir::WalkOrder::PostOrder, mlir::ReverseIterator>(
231  [&](Operation *op) {
232  auto inst = dyn_cast<InstanceOp>(op);
233  // For everything that's not an instance, remove if in slice.
234  if (!inst) {
235  if (slice.contains(op)) {
236  ++numErasedOps;
237  changes = true;
238  op->erase();
239  }
240  return;
241  }
242  // Handle all instances, regardless of presence in slice.
243 
244  // All input probes will be removed.
245  // The processing of the instantiated module ensures these are dead.
246  ImplicitLocOpBuilder builder(inst.getLoc(), inst);
247  builder.setInsertionPointAfter(op);
248  BitVector instPortsToErase(inst.getNumResults());
249  for (auto [idx, result] : llvm::enumerate(inst.getResults())) {
250  if (inst.getPortDirection(idx) == Direction::Out)
251  continue;
252  if (!type_isa<RefType>(result.getType()))
253  continue;
254  instPortsToErase.set(idx);
255 
256  // Convert to wire if not (newly) dead -- there's some local flow
257  // that uses them, perhaps what was previously a u-turn/passthrough.
258  if (result.use_empty())
259  continue;
260 
261  auto wire = builder.create<WireOp>(result.getType());
262  result.replaceAllUsesWith(wire.getDataRaw());
263  }
264  if (instPortsToErase.none())
265  return;
266  changes = true;
267  auto newInst = inst.erasePorts(builder, instPortsToErase);
268  // Keep InstanceGraph up-to-date if available. Assumes safe to update
269  // distinct entries from multiple threads.
270  if (ig)
271  ig->get().replaceInstance(inst, newInst);
272  inst.erase();
273  });
274 
275  numErasedPorts += portsToErase.count();
276  mod.erasePorts(portsToErase);
277 
278  return changes;
279 }
assert(baseType &&"element must be base type")
Builder builder
Forward slice of input probes.
Definition: ProbeDCE.cpp:87
const DenseSet< Operation * > & get() const
Definition: ProbeDCE.cpp:131
LogicalResult chaseVal(SmallVectorImpl< Operation * > &worklist, Value v)
Upwards chase for connect, and chase all users.
Definition: ProbeDCE.cpp:108
size_t size() const
Definition: ProbeDCE.cpp:129
DenseSet< Operation * > slice
Definition: ProbeDCE.cpp:89
LogicalResult add(BlockArgument arg)
Forward slice through the given input probe argument, diagnosing illegal/unsupported uses if encounte...
Definition: ProbeDCE.cpp:135
void chaseUsers(SmallVectorImpl< Operation * > &worklist, Value v)
Forward slice through value -> users.
Definition: ProbeDCE.cpp:102
BlockArgument currentSliceSource
Definition: ProbeDCE.cpp:92
void chase(SmallVectorImpl< Operation * > &worklist, Operation *op)
Operation is in forward slice, add.
Definition: ProbeDCE.cpp:95
bool contains(Operation *op) const
Definition: ProbeDCE.cpp:127
def connect(destination, source)
Definition: support.py:37
std::unique_ptr< mlir::Pass > createProbeDCEPass()
This is the pass constructor.
Definition: ProbeDCE.cpp:78
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21
mlir::raw_indented_ostream & dbgs()
Definition: Utility.h:28