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"
26 #define DEBUG_TYPE "firrtl-imdeadcodeelim"
30 #define GEN_PASS_DEF_IMDEADCODEELIM
31 #include "circt/Dialect/FIRRTL/Passes.h.inc"
35 using namespace circt;
36 using namespace firrtl;
40 return !(mlir::isMemoryEffectFree(op) ||
41 mlir::hasSingleEffect<mlir::MemoryEffects::Allocate>(op) ||
42 mlir::hasSingleEffect<mlir::MemoryEffects::Read>(op));
47 return isa<WireOp, RegResetOp, RegOp, NodeOp, MemOp>(op);
52 if (
auto name = dyn_cast<FNamableOp>(op))
53 if (!name.hasDroppableName())
59 struct IMDeadCodeElimPass
60 :
public circt::firrtl::impl::IMDeadCodeElimBase<IMDeadCodeElimPass> {
61 void runOnOperation()
override;
63 void rewriteModuleSignature(FModuleOp module);
64 void rewriteModuleBody(FModuleOp module);
65 void eraseEmptyModule(FModuleOp module);
66 void forwardConstantOutputPort(FModuleOp module);
69 bool isKnownAlive(Value value)
const {
70 assert(value &&
"null should not be used");
71 return liveElements.count(value);
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); });
82 bool isBlockExecutable(Block *block)
const {
83 return executableBlocks.count(block);
86 void visitUser(Operation *op);
87 void visitValue(Value value);
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>());
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);
106 DenseSet<Block *> executableBlocks;
112 std::variant<Value, FModuleOp, InstanceOp, hw::HierPathOp>;
114 void markAlive(ElementType element) {
115 if (!liveElements.insert(element).second)
117 worklist.push_back(element);
122 SmallVector<ElementType, 64> worklist;
123 llvm::DenseSet<ElementType> liveElements;
127 DenseMap<InstanceOp, SmallVector<hw::HierPathOp>> instanceToHierPaths;
130 DenseMap<hw::HierPathOp, SetVector<ElementType>> hierPathToElements;
134 mlir::SymbolTable *symbolTable;
138 void IMDeadCodeElimPass::visitInstanceOp(InstanceOp instance) {
139 markBlockUndeletable(instance);
141 auto module = instance.getReferencedModule<FModuleOp>(*instanceGraph);
150 for (
auto hierPath : instanceToHierPaths[instance])
154 for (
auto &blockArg : module.getBody().getArguments()) {
155 auto portNo = blockArg.getArgNumber();
157 isKnownAlive(module.getArgument(portNo)))
158 markAlive(instance.getResult(portNo));
162 void IMDeadCodeElimPass::visitModuleOp(FModuleOp module) {
164 for (
auto *use : instanceGraph->lookup(module)->uses())
165 markAlive(cast<InstanceOp>(*use->getInstance()));
168 void IMDeadCodeElimPass::visitHierPathOp(hw::HierPathOp hierPathOp) {
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))
177 for (
auto elem : hierPathToElements[hierPathOp])
181 void IMDeadCodeElimPass::markDeclaration(Operation *op) {
184 for (
auto result : op->getResults())
186 markBlockUndeletable(op);
190 void IMDeadCodeElimPass::markUnknownSideEffectOp(Operation *op) {
193 for (
auto result : op->getResults())
195 for (
auto operand : op->getOperands())
197 markBlockUndeletable(op);
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);
208 void IMDeadCodeElimPass::markInstanceOp(InstanceOp instance) {
210 Operation *op = instance.getReferencedModule(*instanceGraph);
214 if (!isa<FModuleOp>(op)) {
215 auto module = dyn_cast<FModuleLike>(op);
216 for (
auto resultNo : llvm::seq(0u, instance.getNumResults())) {
222 markAlive(instance.getResult(resultNo));
230 auto fModule = cast<FModuleOp>(op);
231 markBlockExecutable(fModule.getBodyBlock());
234 void IMDeadCodeElimPass::markObjectOp(ObjectOp
object) {
239 void IMDeadCodeElimPass::markBlockExecutable(Block *block) {
240 if (!executableBlocks.insert(block).second)
243 auto fmodule = cast<FModuleOp>(block->getParentOp());
244 if (fmodule.isPublic())
248 for (
auto blockArg : block->getArguments())
254 for (
auto &op : *block) {
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))
265 markUnknownSideEffectOp(&op);
271 void IMDeadCodeElimPass::forwardConstantOutputPort(FModuleOp module) {
273 SmallVector<std::pair<unsigned, APSInt>> constantPortIndicesAndValues;
274 auto ports = module.getPorts();
275 auto *instanceGraphNode = instanceGraph->lookup(module);
277 for (
const auto &e : llvm::enumerate(ports)) {
278 unsigned index = e.index();
279 auto port = e.value();
280 auto arg = module.getArgument(index);
288 if (
auto constant =
connect.getSrc().getDefiningOp<ConstantOp>())
289 constantPortIndicesAndValues.push_back({index, constant.getValue()});
293 if (constantPortIndicesAndValues.empty())
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");
305 result.replaceAllUsesWith(builder.create<ConstantOp>(constant));
310 void IMDeadCodeElimPass::runOnOperation() {
312 auto circuits = getOperation().getOps<CircuitOp>();
313 if (circuits.empty())
316 auto circuit = *circuits.begin();
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();
326 instanceGraph = &getChildAnalysis<InstanceGraph>(circuit);
327 symbolTable = &getChildAnalysis<SymbolTable>(circuit);
328 auto &istc = getChildAnalysis<hw::InnerSymbolTableCollection>(circuit);
331 innerRefNamespace = &theInnerRefNamespace;
334 getOperation().walk([&](Operation *op) {
335 if (isa<FModuleOp>(op))
338 if (
auto hierPath = dyn_cast<hw::HierPathOp>(op)) {
339 auto namePath = hierPath.getNamepath().getValue();
342 if (hierPath.isPublic() || namePath.size() <= 1 ||
343 isa<hw::InnerRefAttr>(namePath.back()))
344 return markAlive(hierPath);
347 dyn_cast_or_null<firrtl::InstanceOp>(innerRefNamespace->lookupOp(
348 cast<hw::InnerRefAttr>(namePath.drop_back().back()))))
349 instanceToHierPaths[instance].push_back(hierPath);
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)))
362 if (auto flatSymbolRefAttr = dyn_cast<FlatSymbolRefAttr>(subAttr))
363 if (auto hierPath = symbolTable->template lookup<hw::HierPathOp>(
364 flatSymbolRefAttr.getAttr()))
373 SmallVector<FModuleOp, 0> modules(llvm::make_filter_range(
375 llvm::post_order(instanceGraph),
376 [](
auto *node) {
return dyn_cast<FModuleOp>(*node->getModule()); }),
377 [](
auto module) {
return module; }));
381 for (
auto module : modules)
382 forwardConstantOutputPort(module);
384 for (
auto module : circuit.getBodyBlock()->getOps<FModuleOp>()) {
386 if (module.isPublic()) {
387 markBlockExecutable(module.getBodyBlock());
388 for (
auto port : module.getBodyBlock()->getArguments())
394 auto visitAnnotation = [&](
int portId,
Annotation anno) ->
bool {
395 auto hierPathSym = anno.getMember<FlatSymbolRefAttr>(
"circt.nonlocal");
396 hw::HierPathOp hierPathOp;
399 symbolTable->template lookup<hw::HierPathOp>(hierPathSym.getAttr());
401 if (anno.canBeDeleted()) {
402 if (hierPathOp && portId >= 0)
403 hierPathToElements[hierPathOp].insert(module.getArgument(portId));
407 markAlive(hierPathOp);
409 markAlive(module.getArgument(portId));
416 module, std::bind(visitAnnotation, -1, std::placeholders::_1));
420 while (!worklist.empty()) {
421 auto v = worklist.pop_back_val();
422 if (
auto *value = std::get_if<Value>(&v))
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);
433 for (
auto module : llvm::make_early_inc_range(
434 circuit.getBodyBlock()->getOps<FModuleOp>())) {
435 if (isBlockExecutable(module.getBodyBlock()))
436 rewriteModuleSignature(module);
447 mlir::parallelForEach(circuit.getContext(),
448 circuit.getBodyBlock()->getOps<FModuleOp>(),
449 [&](
auto op) { rewriteModuleBody(op); });
452 for (
auto op : llvm::make_early_inc_range(
453 circuit.getBodyBlock()->getOps<hw::HierPathOp>()))
454 if (!liveElements.count(op))
457 for (
auto module : modules)
458 eraseEmptyModule(module);
461 executableBlocks.clear();
462 liveElements.clear();
463 instanceToHierPaths.clear();
464 hierPathToElements.clear();
467 void IMDeadCodeElimPass::visitValue(Value value) {
468 assert(isKnownAlive(value) &&
"only alive values reach here");
471 for (Operation *user : value.getUsers())
475 if (
auto blockArg = dyn_cast<BlockArgument>(value)) {
476 auto module = cast<FModuleOp>(blockArg.getParentBlock()->getParentOp());
477 auto portDirection = module.getPortDirection(blockArg.getArgNumber());
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()));
493 if (
auto instance = value.getDefiningOp<InstanceOp>()) {
494 auto instanceResult = cast<mlir::OpResult>(value);
496 auto module = instance.getReferencedModule<FModuleOp>(*instanceGraph);
499 if (!module || module.getPortDirection(instanceResult.getResultNumber()) ==
505 BlockArgument modulePortVal =
506 module.getArgument(instanceResult.getResultNumber());
507 return markAlive(modulePortVal);
511 if (
auto mem = value.getDefiningOp<MemOp>()) {
512 for (
auto port : mem->getResults())
518 if (
auto op = value.getDefiningOp())
519 for (
auto operand : op->getOperands())
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());
531 void IMDeadCodeElimPass::visitConnect(FConnectLike
connect) {
533 if (isKnownAlive(
connect.getDest()))
537 void IMDeadCodeElimPass::visitSubelement(Operation *op) {
538 if (isKnownAlive(op->getOperand(0)))
539 markAlive(op->getResult(0));
542 void IMDeadCodeElimPass::rewriteModuleBody(FModuleOp module) {
543 auto *body = module.getBodyBlock();
544 assert(isBlockExecutable(body) &&
545 "unreachable modules must be already deleted");
547 auto removeDeadNonLocalAnnotations = [&](
int _,
Annotation anno) ->
bool {
548 auto hierPathSym = anno.getMember<FlatSymbolRefAttr>(
"circt.nonlocal");
551 if (!anno.canBeDeleted() || !hierPathSym)
554 symbolTable->template lookup<hw::HierPathOp>(hierPathSym.getAttr());
555 return !liveElements.count(hierPathOp);
558 AnnotationSet::removePortAnnotations(module, removeDeadNonLocalAnnotations);
559 AnnotationSet::removeAnnotations(
561 std::bind(removeDeadNonLocalAnnotations, -1, std::placeholders::_1));
564 for (
auto &op : llvm::make_early_inc_range(llvm::reverse(*body))) {
566 if (
auto connect = dyn_cast<FConnectLike>(op)) {
567 if (isAssumedDead(
connect.getDest())) {
568 LLVM_DEBUG(llvm::dbgs() <<
"DEAD: " <<
connect <<
"\n";);
577 isAssumedDead(&op)) {
578 LLVM_DEBUG(llvm::dbgs() <<
"DEAD: " << op <<
"\n";);
579 assert(op.use_empty() &&
"users should be already removed");
586 if (mlir::isOpTriviallyDead(&op)) {
593 void IMDeadCodeElimPass::rewriteModuleSignature(FModuleOp module) {
594 assert(isBlockExecutable(module.getBodyBlock()) &&
595 "unreachable modules must be already deleted");
597 LLVM_DEBUG(llvm::dbgs() <<
"Prune ports of module: " << module.getName()
600 auto replaceInstanceResultWithWire = [&](ImplicitLocOpBuilder &builder,
602 InstanceOp instance) {
603 auto result = instance.getResult(index);
604 if (isAssumedDead(result)) {
608 .create<mlir::UnrealizedConversionCastOp>(
609 ArrayRef<Type>{result.getType()}, ArrayRef<Value>{})
611 result.replaceAllUsesWith(wire);
615 Value wire = builder.create<WireOp>(result.getType()).getResult();
616 result.replaceAllUsesWith(wire);
620 liveElements.erase(result);
621 liveElements.insert(wire);
625 for (
auto *use : llvm::make_early_inc_range(instanceGraphNode->
uses())) {
626 auto instance = cast<InstanceOp>(*use->getInstance());
627 if (!liveElements.count(instance)) {
629 ImplicitLocOpBuilder builder(instance.getLoc(), instance);
630 for (
auto index : llvm::seq(0u, instance.getNumResults()))
631 replaceInstanceResultWithWire(builder, index, instance);
639 if (module.isPublic())
642 unsigned numOldPorts = module.getNumPorts();
643 llvm::BitVector deadPortIndexes(numOldPorts);
645 ImplicitLocOpBuilder builder(module.getLoc(), module.getContext());
646 builder.setInsertionPointToStart(module.getBodyBlock());
647 auto oldPorts = module.getPorts();
649 for (
auto index : llvm::seq(0u, numOldPorts)) {
650 auto argument = module.getArgument(index);
652 "If the port has don't touch, it should be known alive");
658 if (isKnownAlive(argument)) {
662 if (module.getPortDirection(index) == Direction::In)
667 if (llvm::any_of(instanceGraph->lookup(module)->uses(),
670 record->getInstance()->getResult(index));
676 auto wire = builder.create<WireOp>(argument.getType()).getResult();
679 liveElements.erase(argument);
680 liveElements.insert(wire);
681 argument.replaceAllUsesWith(wire);
682 deadPortIndexes.set(index);
689 .create<mlir::UnrealizedConversionCastOp>(
690 ArrayRef<Type>{argument.getType()}, ArrayRef<Value>{})
693 argument.replaceAllUsesWith(wire);
694 assert(isAssumedDead(wire) &&
"dummy wire must be dead");
695 deadPortIndexes.set(index);
699 if (deadPortIndexes.none())
704 for (
auto arg : module.getArguments())
705 liveElements.erase(arg);
708 module.erasePorts(deadPortIndexes);
711 for (
auto arg : module.getArguments())
712 liveElements.insert(arg);
715 for (
auto *use : llvm::make_early_inc_range(instanceGraphNode->
uses())) {
716 auto instance = cast<InstanceOp>(*use->getInstance());
717 ImplicitLocOpBuilder builder(instance.getLoc(), instance);
719 for (
auto index : deadPortIndexes.set_bits())
720 replaceInstanceResultWithWire(builder, index, instance);
724 for (
auto oldResult : instance.getResults())
725 liveElements.erase(oldResult);
728 auto newInstance = instance.erasePorts(builder, deadPortIndexes);
731 for (
auto newResult : newInstance.getResults())
732 liveElements.insert(newResult);
734 instanceGraph->replaceInstance(instance, newInstance);
735 if (liveElements.contains(instance)) {
736 liveElements.erase(instance);
737 liveElements.insert(newInstance);
743 numRemovedPorts += deadPortIndexes.count();
746 void IMDeadCodeElimPass::eraseEmptyModule(FModuleOp module) {
748 if (!module.getBodyBlock()->empty())
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";
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();
767 if (!module.getBodyBlock()->args_empty()) {
768 auto diag = module.emitWarning()
769 <<
"module `" << module.getName()
770 <<
"` is empty but cannot be removed because the "
772 llvm::interleaveComma(module.getPortNames(), diag);
773 diag <<
" are referenced by name or dontTouched";
778 LLVM_DEBUG(llvm::dbgs() <<
"Erase " << module.getName() <<
"\n");
781 instanceGraph->lookup(module.getModuleNameAttr());
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());
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";
805 instanceGraph->erase(instanceGraphNode);
811 return std::make_unique<IMDeadCodeElimPass>();
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.
def connect(destination, source)
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
bool hasDontTouch(Value value)
Check whether a block argument ("port") or the operation defining a value has a DontTouch annotation,...
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.
llvm::raw_ostream & debugPassHeader(const mlir::Pass *pass, int width=80)
Write a boilerplate header for a pass to the debug stream.
This class represents the namespace in which InnerRef's can be resolved.