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