CIRCT  20.0.0git
IMDeadCodeElim.cpp
Go to the documentation of this file.
1 //===- IMDeadCodeElim.cpp - Intermodule Dead Code Elimination ---*- 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 
13 #include "circt/Dialect/HW/HWOps.h"
15 #include "circt/Support/Debug.h"
16 #include "mlir/IR/ImplicitLocOpBuilder.h"
17 #include "mlir/IR/Threading.h"
18 #include "mlir/Interfaces/SideEffectInterfaces.h"
19 #include "mlir/Pass/Pass.h"
20 #include "llvm/ADT/BitVector.h"
21 #include "llvm/ADT/DenseMapInfoVariant.h"
22 #include "llvm/ADT/PostOrderIterator.h"
23 #include "llvm/ADT/TinyPtrVector.h"
24 #include "llvm/Support/Debug.h"
25 
26 #define DEBUG_TYPE "firrtl-imdeadcodeelim"
27 
28 namespace circt {
29 namespace firrtl {
30 #define GEN_PASS_DEF_IMDEADCODEELIM
31 #include "circt/Dialect/FIRRTL/Passes.h.inc"
32 } // namespace firrtl
33 } // namespace circt
34 
35 using namespace circt;
36 using namespace firrtl;
37 
38 // Return true if this op has side-effects except for alloc and read.
39 static bool hasUnknownSideEffect(Operation *op) {
40  return !(mlir::isMemoryEffectFree(op) ||
41  mlir::hasSingleEffect<mlir::MemoryEffects::Allocate>(op) ||
42  mlir::hasSingleEffect<mlir::MemoryEffects::Read>(op));
43 }
44 
45 /// Return true if this is a wire or a register or a node.
46 static bool isDeclaration(Operation *op) {
47  return isa<WireOp, RegResetOp, RegOp, NodeOp, MemOp>(op);
48 }
49 
50 /// Return true if this is a wire or register we're allowed to delete.
51 static bool isDeletableDeclaration(Operation *op) {
52  if (auto name = dyn_cast<FNamableOp>(op))
53  if (!name.hasDroppableName())
54  return false;
55  return !hasDontTouch(op) && AnnotationSet(op).canBeDeleted();
56 }
57 
58 namespace {
59 struct IMDeadCodeElimPass
60  : public circt::firrtl::impl::IMDeadCodeElimBase<IMDeadCodeElimPass> {
61  void runOnOperation() override;
62 
63  void rewriteModuleSignature(FModuleOp module);
64  void rewriteModuleBody(FModuleOp module);
65  void eraseEmptyModule(FModuleOp module);
66  void forwardConstantOutputPort(FModuleOp module);
67 
68  /// Return true if the value is known alive.
69  bool isKnownAlive(Value value) const {
70  assert(value && "null should not be used");
71  return liveElements.count(value);
72  }
73 
74  /// Return true if the value is assumed dead.
75  bool isAssumedDead(Value value) const { return !isKnownAlive(value); }
76  bool isAssumedDead(Operation *op) const {
77  return llvm::none_of(op->getResults(),
78  [&](Value value) { return isKnownAlive(value); });
79  }
80 
81  /// Return true if the block is alive.
82  bool isBlockExecutable(Block *block) const {
83  return executableBlocks.count(block);
84  }
85 
86  void visitUser(Operation *op);
87  void visitValue(Value value);
88 
89  void visitConnect(FConnectLike connect);
90  void visitSubelement(Operation *op);
91  void markBlockExecutable(Block *block);
92  void markBlockUndeletable(Operation *op) {
93  markAlive(op->getParentOfType<FModuleOp>());
94  }
95 
96  void markDeclaration(Operation *op);
97  void markInstanceOp(InstanceOp instanceOp);
98  void markObjectOp(ObjectOp objectOp);
99  void markUnknownSideEffectOp(Operation *op);
100  void visitInstanceOp(InstanceOp instance);
101  void visitHierPathOp(hw::HierPathOp hierpath);
102  void visitModuleOp(FModuleOp module);
103 
104 private:
105  /// The set of blocks that are known to execute, or are intrinsically alive.
106  DenseSet<Block *> executableBlocks;
107 
108  InstanceGraph *instanceGraph;
109 
110  // The type with which we associate liveness.
111  using ElementType =
112  std::variant<Value, FModuleOp, InstanceOp, hw::HierPathOp>;
113 
114  void markAlive(ElementType element) {
115  if (!liveElements.insert(element).second)
116  return;
117  worklist.push_back(element);
118  }
119 
120  /// A worklist of values whose liveness recently changed, indicating
121  /// the users need to be reprocessed.
122  SmallVector<ElementType, 64> worklist;
123  llvm::DenseSet<ElementType> liveElements;
124 
125  /// A map from instances to hierpaths whose last path is the associated
126  /// instance.
127  DenseMap<InstanceOp, SmallVector<hw::HierPathOp>> instanceToHierPaths;
128 
129  /// Hierpath to its users (=non-local annotation targets).
130  DenseMap<hw::HierPathOp, SetVector<ElementType>> hierPathToElements;
131 
132  /// A cache for a (inner)symbol lookp.
133  circt::hw::InnerRefNamespace *innerRefNamespace;
134  mlir::SymbolTable *symbolTable;
135 };
136 } // namespace
137 
138 void IMDeadCodeElimPass::visitInstanceOp(InstanceOp instance) {
139  markBlockUndeletable(instance);
140 
141  auto module = instance.getReferencedModule<FModuleOp>(*instanceGraph);
142 
143  if (!module)
144  return;
145 
146  // NOTE: Don't call `markAlive(module)` here as liveness of instance doesn't
147  // imply the global liveness of the module.
148 
149  // Propgate liveness through hierpath.
150  for (auto hierPath : instanceToHierPaths[instance])
151  markAlive(hierPath);
152 
153  // Input ports get alive only when the instance is alive.
154  for (auto &blockArg : module.getBody().getArguments()) {
155  auto portNo = blockArg.getArgNumber();
156  if (module.getPortDirection(portNo) == Direction::In &&
157  isKnownAlive(module.getArgument(portNo)))
158  markAlive(instance.getResult(portNo));
159  }
160 }
161 
162 void IMDeadCodeElimPass::visitModuleOp(FModuleOp module) {
163  // If the module needs to be alive, so are its instances.
164  for (auto *use : instanceGraph->lookup(module)->uses())
165  markAlive(cast<InstanceOp>(*use->getInstance()));
166 }
167 
168 void IMDeadCodeElimPass::visitHierPathOp(hw::HierPathOp hierPathOp) {
169  // If the hierpath is alive, mark all instances on the path alive.
170  for (auto path : hierPathOp.getNamepathAttr())
171  if (auto innerRef = dyn_cast<hw::InnerRefAttr>(path)) {
172  auto *op = innerRefNamespace->lookupOp(innerRef);
173  if (auto instance = dyn_cast_or_null<InstanceOp>(op))
174  markAlive(instance);
175  }
176 
177  for (auto elem : hierPathToElements[hierPathOp])
178  markAlive(elem);
179 }
180 
181 void IMDeadCodeElimPass::markDeclaration(Operation *op) {
182  assert(isDeclaration(op) && "only a declaration is expected");
183  if (!isDeletableDeclaration(op)) {
184  for (auto result : op->getResults())
185  markAlive(result);
186  markBlockUndeletable(op);
187  }
188 }
189 
190 void IMDeadCodeElimPass::markUnknownSideEffectOp(Operation *op) {
191  // For operations with side effects, pessimistically mark results and
192  // operands as alive.
193  for (auto result : op->getResults())
194  markAlive(result);
195  for (auto operand : op->getOperands())
196  markAlive(operand);
197  markBlockUndeletable(op);
198 }
199 
200 void IMDeadCodeElimPass::visitUser(Operation *op) {
201  LLVM_DEBUG(llvm::dbgs() << "Visit: " << *op << "\n");
202  if (auto connectOp = dyn_cast<FConnectLike>(op))
203  return visitConnect(connectOp);
204  if (isa<SubfieldOp, SubindexOp, SubaccessOp, ObjectSubfieldOp>(op))
205  return visitSubelement(op);
206 }
207 
208 void IMDeadCodeElimPass::markInstanceOp(InstanceOp instance) {
209  // Get the module being referenced.
210  Operation *op = instance.getReferencedModule(*instanceGraph);
211 
212  // If this is an extmodule, just remember that any inputs and inouts are
213  // alive.
214  if (!isa<FModuleOp>(op)) {
215  auto module = dyn_cast<FModuleLike>(op);
216  for (auto resultNo : llvm::seq(0u, instance.getNumResults())) {
217  // If this is an output to the extmodule, we can ignore it.
218  if (module.getPortDirection(resultNo) == Direction::Out)
219  continue;
220 
221  // Otherwise this is an input from it or an inout, mark it as alive.
222  markAlive(instance.getResult(resultNo));
223  }
224  markAlive(instance);
225 
226  return;
227  }
228 
229  // Otherwise this is a defined module.
230  auto fModule = cast<FModuleOp>(op);
231  markBlockExecutable(fModule.getBodyBlock());
232 }
233 
234 void IMDeadCodeElimPass::markObjectOp(ObjectOp object) {
235  // unconditionally keep all objects alive.
236  markAlive(object);
237 }
238 
239 void IMDeadCodeElimPass::markBlockExecutable(Block *block) {
240  if (!executableBlocks.insert(block).second)
241  return; // Already executable.
242 
243  auto fmodule = cast<FModuleOp>(block->getParentOp());
244  if (fmodule.isPublic())
245  markAlive(fmodule);
246 
247  // Mark ports with don't touch as alive.
248  for (auto blockArg : block->getArguments())
249  if (hasDontTouch(blockArg)) {
250  markAlive(blockArg);
251  markAlive(fmodule);
252  }
253 
254  for (auto &op : *block) {
255  if (isDeclaration(&op))
256  markDeclaration(&op);
257  else if (auto instance = dyn_cast<InstanceOp>(op))
258  markInstanceOp(instance);
259  else if (auto object = dyn_cast<ObjectOp>(op))
260  markObjectOp(object);
261  else if (isa<FConnectLike>(op))
262  // Skip connect op.
263  continue;
264  else if (hasUnknownSideEffect(&op))
265  markUnknownSideEffectOp(&op);
266 
267  // TODO: Handle attach etc.
268  }
269 }
270 
271 void IMDeadCodeElimPass::forwardConstantOutputPort(FModuleOp module) {
272  // This tracks constant values of output ports.
273  SmallVector<std::pair<unsigned, APSInt>> constantPortIndicesAndValues;
274  auto ports = module.getPorts();
275  auto *instanceGraphNode = instanceGraph->lookup(module);
276 
277  for (const auto &e : llvm::enumerate(ports)) {
278  unsigned index = e.index();
279  auto port = e.value();
280  auto arg = module.getArgument(index);
281 
282  // If the port has don't touch, don't propagate the constant value.
283  if (!port.isOutput() || hasDontTouch(arg))
284  continue;
285 
286  // Remember the index and constant value connected to an output port.
287  if (auto connect = getSingleConnectUserOf(arg))
288  if (auto constant = connect.getSrc().getDefiningOp<ConstantOp>())
289  constantPortIndicesAndValues.push_back({index, constant.getValue()});
290  }
291 
292  // If there is no constant port, abort.
293  if (constantPortIndicesAndValues.empty())
294  return;
295 
296  // Rewrite all uses.
297  for (auto *use : instanceGraphNode->uses()) {
298  auto instance = cast<InstanceOp>(*use->getInstance());
299  ImplicitLocOpBuilder builder(instance.getLoc(), instance);
300  for (auto [index, constant] : constantPortIndicesAndValues) {
301  auto result = instance.getResult(index);
302  assert(ports[index].isOutput() && "must be an output port");
303 
304  // Replace the port with the constant.
305  result.replaceAllUsesWith(builder.create<ConstantOp>(constant));
306  }
307  }
308 }
309 
310 void IMDeadCodeElimPass::runOnOperation() {
311  LLVM_DEBUG(debugPassHeader(this) << "\n";);
312  auto circuits = getOperation().getOps<CircuitOp>();
313  if (circuits.empty())
314  return;
315 
316  auto circuit = *circuits.begin();
317 
318  if (!llvm::hasSingleElement(circuits)) {
319  mlir::emitError(circuit.getLoc(),
320  "cannot process multiple circuit operations")
321  .attachNote((*std::next(circuits.begin())).getLoc())
322  << "second circuit here";
323  return signalPassFailure();
324  }
325 
326  instanceGraph = &getChildAnalysis<InstanceGraph>(circuit);
327  symbolTable = &getChildAnalysis<SymbolTable>(circuit);
328  auto &istc = getChildAnalysis<hw::InnerSymbolTableCollection>(circuit);
329 
330  circt::hw::InnerRefNamespace theInnerRefNamespace{*symbolTable, istc};
331  innerRefNamespace = &theInnerRefNamespace;
332 
333  // Walk attributes and find unknown uses of inner symbols or hierpaths.
334  getOperation().walk([&](Operation *op) {
335  if (isa<FModuleOp>(op)) // Port or module annotations are ok to ignore.
336  return;
337 
338  if (auto hierPath = dyn_cast<hw::HierPathOp>(op)) {
339  auto namePath = hierPath.getNamepath().getValue();
340  // If the hierpath is public or ill-formed, the verifier should have
341  // caught the error. Conservatively mark the symbol as alive.
342  if (hierPath.isPublic() || namePath.size() <= 1 ||
343  isa<hw::InnerRefAttr>(namePath.back()))
344  return markAlive(hierPath);
345 
346  if (auto instance =
347  dyn_cast_or_null<firrtl::InstanceOp>(innerRefNamespace->lookupOp(
348  cast<hw::InnerRefAttr>(namePath.drop_back().back()))))
349  instanceToHierPaths[instance].push_back(hierPath);
350  return;
351  }
352 
353  // If there is an unknown use of inner sym or hierpath, just mark all of
354  // them alive.
355  for (NamedAttribute namedAttr : op->getAttrs()) {
356  namedAttr.getValue().walk([&](Attribute subAttr) {
357  if (auto innerRef = dyn_cast<hw::InnerRefAttr>(subAttr))
358  if (auto instance = dyn_cast_or_null<firrtl::InstanceOp>(
359  innerRefNamespace->lookupOp(innerRef)))
360  markAlive(instance);
361 
362  if (auto flatSymbolRefAttr = dyn_cast<FlatSymbolRefAttr>(subAttr))
363  if (auto hierPath = symbolTable->template lookup<hw::HierPathOp>(
364  flatSymbolRefAttr.getAttr()))
365  markAlive(hierPath);
366  });
367  }
368  });
369 
370  // Create a vector of modules in the post order of instance graph.
371  // FIXME: We copy the list of modules into a vector first to avoid iterator
372  // invalidation while we mutate the instance graph. See issue 3387.
373  SmallVector<FModuleOp, 0> modules(llvm::make_filter_range(
374  llvm::map_range(
375  llvm::post_order(instanceGraph),
376  [](auto *node) { return dyn_cast<FModuleOp>(*node->getModule()); }),
377  [](auto module) { return module; }));
378 
379  // Forward constant output ports to caller sides so that we can eliminate
380  // constant outputs.
381  for (auto module : modules)
382  forwardConstantOutputPort(module);
383 
384  for (auto module : circuit.getBodyBlock()->getOps<FModuleOp>()) {
385  // Mark the ports of public modules as alive.
386  if (module.isPublic()) {
387  markBlockExecutable(module.getBodyBlock());
388  for (auto port : module.getBodyBlock()->getArguments())
389  markAlive(port);
390  }
391 
392  // Walk annotations and populate a map from hierpath to attached annotation
393  // targets. `portId` is `-1` for module annotations.
394  auto visitAnnotation = [&](int portId, Annotation anno) -> bool {
395  auto hierPathSym = anno.getMember<FlatSymbolRefAttr>("circt.nonlocal");
396  hw::HierPathOp hierPathOp;
397  if (hierPathSym)
398  hierPathOp =
399  symbolTable->template lookup<hw::HierPathOp>(hierPathSym.getAttr());
400 
401  if (anno.canBeDeleted()) {
402  if (hierPathOp && portId >= 0)
403  hierPathToElements[hierPathOp].insert(module.getArgument(portId));
404  return false;
405  }
406  if (hierPathOp)
407  markAlive(hierPathOp);
408  if (portId >= 0)
409  markAlive(module.getArgument(portId));
410  markAlive(module);
411  return false;
412  };
413 
414  AnnotationSet::removePortAnnotations(module, visitAnnotation);
416  module, std::bind(visitAnnotation, -1, std::placeholders::_1));
417  }
418 
419  // If an element changed liveness then propagate liveness through it.
420  while (!worklist.empty()) {
421  auto v = worklist.pop_back_val();
422  if (auto *value = std::get_if<Value>(&v))
423  visitValue(*value);
424  else if (auto *instance = std::get_if<InstanceOp>(&v))
425  visitInstanceOp(*instance);
426  else if (auto *hierpath = std::get_if<hw::HierPathOp>(&v))
427  visitHierPathOp(*hierpath);
428  else if (auto *module = std::get_if<FModuleOp>(&v))
429  visitModuleOp(*module);
430  }
431 
432  // Rewrite module signatures or delete unreachable modules.
433  for (auto module : llvm::make_early_inc_range(
434  circuit.getBodyBlock()->getOps<FModuleOp>())) {
435  if (isBlockExecutable(module.getBodyBlock()))
436  rewriteModuleSignature(module);
437  else {
438  // If the module is unreachable from the toplevel, just delete it.
439  // Note that post-order traversal on the instance graph never visit
440  // unreachable modules so it's safe to erase the module even though
441  // `modules` seems to be capturing module pointers.
442  module.erase();
443  }
444  }
445 
446  // Rewrite module bodies parallelly.
447  mlir::parallelForEach(circuit.getContext(),
448  circuit.getBodyBlock()->getOps<FModuleOp>(),
449  [&](auto op) { rewriteModuleBody(op); });
450 
451  // Clean up hierpaths.
452  for (auto op : llvm::make_early_inc_range(
453  circuit.getBodyBlock()->getOps<hw::HierPathOp>()))
454  if (!liveElements.count(op))
455  op.erase();
456 
457  for (auto module : modules)
458  eraseEmptyModule(module);
459 
460  // Clean up data structures.
461  executableBlocks.clear();
462  liveElements.clear();
463  instanceToHierPaths.clear();
464  hierPathToElements.clear();
465 }
466 
467 void IMDeadCodeElimPass::visitValue(Value value) {
468  assert(isKnownAlive(value) && "only alive values reach here");
469 
470  // Propagate liveness through users.
471  for (Operation *user : value.getUsers())
472  visitUser(user);
473 
474  // Requiring an input port propagates the liveness to each instance.
475  if (auto blockArg = dyn_cast<BlockArgument>(value)) {
476  auto module = cast<FModuleOp>(blockArg.getParentBlock()->getParentOp());
477  auto portDirection = module.getPortDirection(blockArg.getArgNumber());
478  // If the port is input, it's necessary to mark corresponding input ports of
479  // instances as alive. We don't have to propagate the liveness of output
480  // ports.
481  if (portDirection == Direction::In) {
482  for (auto *instRec : instanceGraph->lookup(module)->uses()) {
483  auto instance = cast<InstanceOp>(instRec->getInstance());
484  if (liveElements.contains(instance))
485  markAlive(instance.getResult(blockArg.getArgNumber()));
486  }
487  }
488  return;
489  }
490 
491  // Marking an instance port as alive propagates to the corresponding port of
492  // the module.
493  if (auto instance = value.getDefiningOp<InstanceOp>()) {
494  auto instanceResult = cast<mlir::OpResult>(value);
495  // Update the src, when it's an instance op.
496  auto module = instance.getReferencedModule<FModuleOp>(*instanceGraph);
497 
498  // Propagate liveness only when a port is output.
499  if (!module || module.getPortDirection(instanceResult.getResultNumber()) ==
500  Direction::In)
501  return;
502 
503  markAlive(instance);
504 
505  BlockArgument modulePortVal =
506  module.getArgument(instanceResult.getResultNumber());
507  return markAlive(modulePortVal);
508  }
509 
510  // If a port of a memory is alive, all other ports are.
511  if (auto mem = value.getDefiningOp<MemOp>()) {
512  for (auto port : mem->getResults())
513  markAlive(port);
514  return;
515  }
516 
517  // If op is defined by an operation, mark its operands as alive.
518  if (auto op = value.getDefiningOp())
519  for (auto operand : op->getOperands())
520  markAlive(operand);
521 
522  // If either result of a forceable declaration is alive, they both are.
523  if (auto fop = value.getDefiningOp<Forceable>();
524  fop && fop.isForceable() &&
525  (fop.getData() == value || fop.getDataRef() == value)) {
526  markAlive(fop.getData());
527  markAlive(fop.getDataRef());
528  }
529 }
530 
531 void IMDeadCodeElimPass::visitConnect(FConnectLike connect) {
532  // If the dest is alive, mark the source value as alive.
533  if (isKnownAlive(connect.getDest()))
534  markAlive(connect.getSrc());
535 }
536 
537 void IMDeadCodeElimPass::visitSubelement(Operation *op) {
538  if (isKnownAlive(op->getOperand(0)))
539  markAlive(op->getResult(0));
540 }
541 
542 void IMDeadCodeElimPass::rewriteModuleBody(FModuleOp module) {
543  auto *body = module.getBodyBlock();
544  assert(isBlockExecutable(body) &&
545  "unreachable modules must be already deleted");
546 
547  auto removeDeadNonLocalAnnotations = [&](int _, Annotation anno) -> bool {
548  auto hierPathSym = anno.getMember<FlatSymbolRefAttr>("circt.nonlocal");
549  // We only clean up non-local annotations here as local annotations will
550  // be deleted afterwards.
551  if (!anno.canBeDeleted() || !hierPathSym)
552  return false;
553  auto hierPathOp =
554  symbolTable->template lookup<hw::HierPathOp>(hierPathSym.getAttr());
555  return !liveElements.count(hierPathOp);
556  };
557 
558  AnnotationSet::removePortAnnotations(module, removeDeadNonLocalAnnotations);
559  AnnotationSet::removeAnnotations(
560  module,
561  std::bind(removeDeadNonLocalAnnotations, -1, std::placeholders::_1));
562 
563  // Walk the IR bottom-up when deleting operations.
564  for (auto &op : llvm::make_early_inc_range(llvm::reverse(*body))) {
565  // Connects to values that we found to be dead can be dropped.
566  if (auto connect = dyn_cast<FConnectLike>(op)) {
567  if (isAssumedDead(connect.getDest())) {
568  LLVM_DEBUG(llvm::dbgs() << "DEAD: " << connect << "\n";);
569  connect.erase();
570  ++numErasedOps;
571  }
572  continue;
573  }
574 
575  // Delete dead wires, regs, nodes and alloc/read ops.
576  if ((isDeclaration(&op) || !hasUnknownSideEffect(&op)) &&
577  isAssumedDead(&op)) {
578  LLVM_DEBUG(llvm::dbgs() << "DEAD: " << op << "\n";);
579  assert(op.use_empty() && "users should be already removed");
580  op.erase();
581  ++numErasedOps;
582  continue;
583  }
584 
585  // Remove non-sideeffect op using `isOpTriviallyDead`.
586  if (mlir::isOpTriviallyDead(&op)) {
587  op.erase();
588  ++numErasedOps;
589  }
590  }
591 }
592 
593 void IMDeadCodeElimPass::rewriteModuleSignature(FModuleOp module) {
594  assert(isBlockExecutable(module.getBodyBlock()) &&
595  "unreachable modules must be already deleted");
596  InstanceGraphNode *instanceGraphNode = instanceGraph->lookup(module);
597  LLVM_DEBUG(llvm::dbgs() << "Prune ports of module: " << module.getName()
598  << "\n");
599 
600  auto replaceInstanceResultWithWire = [&](ImplicitLocOpBuilder &builder,
601  unsigned index,
602  InstanceOp instance) {
603  auto result = instance.getResult(index);
604  if (isAssumedDead(result)) {
605  // If the result is dead, replace the result with an unrealized conversion
606  // cast which works as a dummy placeholder.
607  auto wire = builder
608  .create<mlir::UnrealizedConversionCastOp>(
609  ArrayRef<Type>{result.getType()}, ArrayRef<Value>{})
610  ->getResult(0);
611  result.replaceAllUsesWith(wire);
612  return;
613  }
614 
615  Value wire = builder.create<WireOp>(result.getType()).getResult();
616  result.replaceAllUsesWith(wire);
617  // If a module port is dead but its instance result is alive, the port
618  // is used as a temporary wire so make sure that a replaced wire is
619  // putted into `liveSet`.
620  liveElements.erase(result);
621  liveElements.insert(wire);
622  };
623 
624  // First, delete dead instances.
625  for (auto *use : llvm::make_early_inc_range(instanceGraphNode->uses())) {
626  auto instance = cast<InstanceOp>(*use->getInstance());
627  if (!liveElements.count(instance)) {
628  // Replace old instance results with dummy wires.
629  ImplicitLocOpBuilder builder(instance.getLoc(), instance);
630  for (auto index : llvm::seq(0u, instance.getNumResults()))
631  replaceInstanceResultWithWire(builder, index, instance);
632  // Make sure that we update the instance graph.
633  use->erase();
634  instance.erase();
635  }
636  }
637 
638  // Ports of public modules cannot be modified.
639  if (module.isPublic())
640  return;
641 
642  unsigned numOldPorts = module.getNumPorts();
643  llvm::BitVector deadPortIndexes(numOldPorts);
644 
645  ImplicitLocOpBuilder builder(module.getLoc(), module.getContext());
646  builder.setInsertionPointToStart(module.getBodyBlock());
647  auto oldPorts = module.getPorts();
648 
649  for (auto index : llvm::seq(0u, numOldPorts)) {
650  auto argument = module.getArgument(index);
651  assert((!hasDontTouch(argument) || isKnownAlive(argument)) &&
652  "If the port has don't touch, it should be known alive");
653 
654  // If the port has dontTouch, skip.
655  if (hasDontTouch(argument))
656  continue;
657 
658  if (isKnownAlive(argument)) {
659 
660  // If an output port is only used internally in the module, then we can
661  // remove the port and replace it with a wire.
662  if (module.getPortDirection(index) == Direction::In)
663  continue;
664 
665  // Check if the output port is demanded by any instance. If not, then it
666  // is only demanded internally to the module.
667  if (llvm::any_of(instanceGraph->lookup(module)->uses(),
668  [&](InstanceRecord *record) {
669  return isKnownAlive(
670  record->getInstance()->getResult(index));
671  }))
672  continue;
673 
674  // Ok, this port is used only within its defined module. So we can replace
675  // the port with a wire.
676  auto wire = builder.create<WireOp>(argument.getType()).getResult();
677 
678  // Since `liveSet` contains the port, we have to erase it from the set.
679  liveElements.erase(argument);
680  liveElements.insert(wire);
681  argument.replaceAllUsesWith(wire);
682  deadPortIndexes.set(index);
683  continue;
684  }
685 
686  // Replace the port with a dummy wire. This wire should be erased within
687  // `rewriteModuleBody`.
688  Value wire = builder
689  .create<mlir::UnrealizedConversionCastOp>(
690  ArrayRef<Type>{argument.getType()}, ArrayRef<Value>{})
691  ->getResult(0);
692 
693  argument.replaceAllUsesWith(wire);
694  assert(isAssumedDead(wire) && "dummy wire must be dead");
695  deadPortIndexes.set(index);
696  }
697 
698  // If there is nothing to remove, abort.
699  if (deadPortIndexes.none())
700  return;
701 
702  // Erase arguments of the old module from liveSet to prevent from creating
703  // dangling pointers.
704  for (auto arg : module.getArguments())
705  liveElements.erase(arg);
706 
707  // Delete ports from the module.
708  module.erasePorts(deadPortIndexes);
709 
710  // Add arguments of the new module to liveSet.
711  for (auto arg : module.getArguments())
712  liveElements.insert(arg);
713 
714  // Rewrite all uses.
715  for (auto *use : llvm::make_early_inc_range(instanceGraphNode->uses())) {
716  auto instance = cast<InstanceOp>(*use->getInstance());
717  ImplicitLocOpBuilder builder(instance.getLoc(), instance);
718  // Replace old instance results with dummy wires.
719  for (auto index : deadPortIndexes.set_bits())
720  replaceInstanceResultWithWire(builder, index, instance);
721 
722  // Since we will rewrite instance op, it is necessary to remove old
723  // instance results from liveSet.
724  for (auto oldResult : instance.getResults())
725  liveElements.erase(oldResult);
726 
727  // Create a new instance op without dead ports.
728  auto newInstance = instance.erasePorts(builder, deadPortIndexes);
729 
730  // Mark new results as alive.
731  for (auto newResult : newInstance.getResults())
732  liveElements.insert(newResult);
733 
734  instanceGraph->replaceInstance(instance, newInstance);
735  if (liveElements.contains(instance)) {
736  liveElements.erase(instance);
737  liveElements.insert(newInstance);
738  }
739  // Remove old one.
740  instance.erase();
741  }
742 
743  numRemovedPorts += deadPortIndexes.count();
744 }
745 
746 void IMDeadCodeElimPass::eraseEmptyModule(FModuleOp module) {
747  // If the module is not empty, just skip.
748  if (!module.getBodyBlock()->empty())
749  return;
750 
751  // We cannot delete public modules so generate a warning.
752  if (module.isPublic()) {
753  mlir::emitWarning(module.getLoc())
754  << "module `" << module.getName()
755  << "` is empty but cannot be removed because the module is public";
756  return;
757  }
758 
759  if (!module.getAnnotations().empty()) {
760  module.emitWarning() << "module `" << module.getName()
761  << "` is empty but cannot be removed "
762  "because the module has annotations "
763  << module.getAnnotations();
764  return;
765  }
766 
767  if (!module.getBodyBlock()->args_empty()) {
768  auto diag = module.emitWarning()
769  << "module `" << module.getName()
770  << "` is empty but cannot be removed because the "
771  "module has ports ";
772  llvm::interleaveComma(module.getPortNames(), diag);
773  diag << " are referenced by name or dontTouched";
774  return;
775  }
776 
777  // Ok, the module is empty. Delete instances unless they have symbols.
778  LLVM_DEBUG(llvm::dbgs() << "Erase " << module.getName() << "\n");
779 
780  InstanceGraphNode *instanceGraphNode =
781  instanceGraph->lookup(module.getModuleNameAttr());
782 
783  SmallVector<Location> instancesWithSymbols;
784  for (auto *use : llvm::make_early_inc_range(instanceGraphNode->uses())) {
785  auto instance = cast<InstanceOp>(use->getInstance());
786  if (instance.getInnerSym()) {
787  instancesWithSymbols.push_back(instance.getLoc());
788  continue;
789  }
790  use->erase();
791  instance.erase();
792  }
793 
794  // If there is an instance with a symbol, we don't delete the module itself.
795  if (!instancesWithSymbols.empty()) {
796  auto diag = module.emitWarning()
797  << "module `" << module.getName()
798  << "` is empty but cannot be removed because an instance is "
799  "referenced by name";
800  diag.attachNote(FusedLoc::get(&getContext(), instancesWithSymbols))
801  << "these are instances with symbols";
802  return;
803  }
804 
805  instanceGraph->erase(instanceGraphNode);
806  module.erase();
807  ++numErasedModules;
808 }
809 
810 std::unique_ptr<mlir::Pass> circt::firrtl::createIMDeadCodeElimPass() {
811  return std::make_unique<IMDeadCodeElimPass>();
812 }
assert(baseType &&"element must be base type")
static bool isDeletableDeclaration(Operation *op)
Return true if this is a wire or register we're allowed to delete.
static bool hasUnknownSideEffect(Operation *op)
static bool isDeclaration(Operation *op)
Return true if this is a wire or a register or a node.
This class provides a read-only projection over the MLIR attributes that represent a set of annotatio...
bool removeAnnotations(llvm::function_ref< bool(Annotation)> predicate)
Remove all annotations from this annotation set for which predicate returns true.
static bool removePortAnnotations(Operation *module, llvm::function_ref< bool(unsigned, Annotation)> predicate)
Remove all port annotations from a module or extmodule for which predicate returns true.
bool canBeDeleted() const
Check if every annotation can be deleted.
This class provides a read-only projection of an annotation.
This graph tracks modules and where they are instantiated.
This is a Node in the InstanceGraph.
llvm::iterator_range< UseIterator > uses()
This is an edge in the InstanceGraph.
Definition: InstanceGraph.h:55
def connect(destination, source)
Definition: support.py:39
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition: CalyxOps.cpp:55
bool hasDontTouch(Value value)
Check whether a block argument ("port") or the operation defining a value has a DontTouch annotation,...
Definition: FIRRTLOps.cpp:317
std::unique_ptr< mlir::Pass > createIMDeadCodeElimPass()
MatchingConnectOp getSingleConnectUserOf(Value value)
Scan all the uses of the specified value, checking to see if there is exactly one connect that has th...
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21
llvm::raw_ostream & debugPassHeader(const mlir::Pass *pass, int width=80)
Write a boilerplate header for a pass to the debug stream.
Definition: Debug.cpp:31
This class represents the namespace in which InnerRef's can be resolved.