15 #include "mlir/IR/Iterators.h"
16 #include "mlir/IR/Threading.h"
17 #include "mlir/Interfaces/SideEffectInterfaces.h"
18 #include "mlir/Pass/Pass.h"
19 #include "llvm/ADT/BitVector.h"
20 #include "llvm/ADT/DenseMapInfoVariant.h"
21 #include "llvm/ADT/PostOrderIterator.h"
22 #include "llvm/Support/Debug.h"
24 #define DEBUG_TYPE "firrtl-imdeadcodeelim"
28 #define GEN_PASS_DEF_IMDEADCODEELIM
29 #include "circt/Dialect/FIRRTL/Passes.h.inc"
33 using namespace circt;
34 using namespace firrtl;
38 return !(mlir::isMemoryEffectFree(op) ||
39 mlir::hasSingleEffect<mlir::MemoryEffects::Allocate>(op) ||
40 mlir::hasSingleEffect<mlir::MemoryEffects::Read>(op));
45 return isa<WireOp, RegResetOp, RegOp, NodeOp, MemOp>(op);
50 if (
auto name = dyn_cast<FNamableOp>(op))
51 if (!name.hasDroppableName())
57 struct IMDeadCodeElimPass
58 :
public circt::firrtl::impl::IMDeadCodeElimBase<IMDeadCodeElimPass> {
59 void runOnOperation()
override;
61 void rewriteModuleSignature(FModuleOp module);
62 void rewriteModuleBody(FModuleOp module);
63 void eraseEmptyModule(FModuleOp module);
64 void forwardConstantOutputPort(FModuleOp module);
67 bool isKnownAlive(Value value)
const {
68 assert(value &&
"null should not be used");
69 return liveElements.count(value);
73 bool isAssumedDead(Value value)
const {
return !isKnownAlive(value); }
74 bool isAssumedDead(Operation *op)
const {
75 return llvm::none_of(op->getResults(),
76 [&](Value value) { return isKnownAlive(value); });
80 bool isBlockExecutable(Block *block)
const {
81 return executableBlocks.count(block);
84 void visitUser(Operation *op);
85 void visitValue(Value value);
87 void visitConnect(FConnectLike
connect);
88 void visitSubelement(Operation *op);
89 void markBlockExecutable(Block *block);
90 void markBlockUndeletable(Operation *op) {
91 markAlive(op->getParentOfType<FModuleOp>());
94 void markDeclaration(Operation *op);
95 void markInstanceOp(InstanceOp instanceOp);
96 void markObjectOp(ObjectOp objectOp);
97 void markUnknownSideEffectOp(Operation *op);
98 void visitInstanceOp(InstanceOp instance);
99 void visitHierPathOp(hw::HierPathOp hierpath);
100 void visitModuleOp(FModuleOp module);
104 DenseSet<Block *> executableBlocks;
110 std::variant<Value, FModuleOp, InstanceOp, hw::HierPathOp>;
112 void markAlive(ElementType element) {
113 if (!liveElements.insert(element).second)
115 worklist.push_back(element);
120 SmallVector<ElementType, 64> worklist;
121 llvm::DenseSet<ElementType> liveElements;
125 DenseMap<InstanceOp, SmallVector<hw::HierPathOp>> instanceToHierPaths;
128 DenseMap<hw::HierPathOp, SetVector<ElementType>> hierPathToElements;
132 mlir::SymbolTable *symbolTable;
136 void IMDeadCodeElimPass::visitInstanceOp(InstanceOp instance) {
137 markBlockUndeletable(instance);
139 auto module = instance.getReferencedModule<FModuleOp>(*instanceGraph);
148 for (
auto hierPath : instanceToHierPaths[instance])
152 for (
auto &blockArg : module.getBody().getArguments()) {
153 auto portNo = blockArg.getArgNumber();
155 isKnownAlive(module.getArgument(portNo)))
156 markAlive(instance.getResult(portNo));
160 void IMDeadCodeElimPass::visitModuleOp(FModuleOp module) {
162 for (
auto *use : instanceGraph->lookup(module)->uses())
163 markAlive(cast<InstanceOp>(*use->getInstance()));
166 void IMDeadCodeElimPass::visitHierPathOp(hw::HierPathOp hierPathOp) {
168 for (
auto path : hierPathOp.getNamepathAttr())
169 if (
auto innerRef = dyn_cast<hw::InnerRefAttr>(path)) {
170 auto *op = innerRefNamespace->lookupOp(innerRef);
171 if (
auto instance = dyn_cast_or_null<InstanceOp>(op))
175 for (
auto elem : hierPathToElements[hierPathOp])
179 void IMDeadCodeElimPass::markDeclaration(Operation *op) {
182 for (
auto result : op->getResults())
184 markBlockUndeletable(op);
188 void IMDeadCodeElimPass::markUnknownSideEffectOp(Operation *op) {
191 for (
auto result : op->getResults())
193 for (
auto operand : op->getOperands())
195 markBlockUndeletable(op);
198 void IMDeadCodeElimPass::visitUser(Operation *op) {
199 LLVM_DEBUG(llvm::dbgs() <<
"Visit: " << *op <<
"\n");
200 if (
auto connectOp = dyn_cast<FConnectLike>(op))
201 return visitConnect(connectOp);
202 if (isa<SubfieldOp, SubindexOp, SubaccessOp, ObjectSubfieldOp>(op))
203 return visitSubelement(op);
206 void IMDeadCodeElimPass::markInstanceOp(InstanceOp instance) {
208 Operation *op = instance.getReferencedModule(*instanceGraph);
212 if (!isa<FModuleOp>(op)) {
213 auto module = dyn_cast<FModuleLike>(op);
214 for (
auto resultNo : llvm::seq(0u, instance.getNumResults())) {
220 markAlive(instance.getResult(resultNo));
228 auto fModule = cast<FModuleOp>(op);
229 markBlockExecutable(fModule.getBodyBlock());
232 void IMDeadCodeElimPass::markObjectOp(ObjectOp
object) {
237 void IMDeadCodeElimPass::markBlockExecutable(Block *block) {
238 if (!executableBlocks.insert(block).second)
241 auto fmodule = dyn_cast<FModuleOp>(block->getParentOp());
242 if (fmodule && fmodule.isPublic())
246 for (
auto blockArg : block->getArguments())
253 for (
auto &op : *block) {
255 markDeclaration(&op);
256 else if (
auto instance = dyn_cast<InstanceOp>(op))
257 markInstanceOp(instance);
258 else if (
auto object = dyn_cast<ObjectOp>(op))
259 markObjectOp(
object);
260 else if (isa<FConnectLike>(op))
264 markUnknownSideEffectOp(&op);
267 for (
auto ®ion : op.getRegions())
268 for (
auto &block : region.getBlocks())
269 markBlockExecutable(&block);
276 void IMDeadCodeElimPass::forwardConstantOutputPort(FModuleOp module) {
278 SmallVector<std::pair<unsigned, APSInt>> constantPortIndicesAndValues;
279 auto ports = module.getPorts();
280 auto *instanceGraphNode = instanceGraph->lookup(module);
282 for (
const auto &e : llvm::enumerate(ports)) {
283 unsigned index = e.index();
284 auto port = e.value();
285 auto arg = module.getArgument(index);
293 if (
auto constant =
connect.getSrc().getDefiningOp<ConstantOp>())
294 constantPortIndicesAndValues.push_back({index, constant.getValue()});
298 if (constantPortIndicesAndValues.empty())
302 for (
auto *use : instanceGraphNode->uses()) {
303 auto instance = cast<InstanceOp>(*use->getInstance());
304 ImplicitLocOpBuilder builder(instance.getLoc(), instance);
305 for (
auto [index, constant] : constantPortIndicesAndValues) {
306 auto result = instance.getResult(index);
307 assert(ports[index].isOutput() &&
"must be an output port");
310 result.replaceAllUsesWith(builder.create<ConstantOp>(constant));
315 void IMDeadCodeElimPass::runOnOperation() {
317 auto circuits = getOperation().getOps<CircuitOp>();
318 if (circuits.empty())
321 auto circuit = *circuits.begin();
323 if (!llvm::hasSingleElement(circuits)) {
324 mlir::emitError(circuit.getLoc(),
325 "cannot process multiple circuit operations")
326 .attachNote((*std::next(circuits.begin())).getLoc())
327 <<
"second circuit here";
328 return signalPassFailure();
331 instanceGraph = &getChildAnalysis<InstanceGraph>(circuit);
332 symbolTable = &getChildAnalysis<SymbolTable>(circuit);
333 auto &istc = getChildAnalysis<hw::InnerSymbolTableCollection>(circuit);
336 innerRefNamespace = &theInnerRefNamespace;
339 getOperation().walk([&](Operation *op) {
340 if (isa<FModuleOp>(op))
343 if (
auto hierPath = dyn_cast<hw::HierPathOp>(op)) {
344 auto namePath = hierPath.getNamepath().getValue();
347 if (hierPath.isPublic() || namePath.size() <= 1 ||
348 isa<hw::InnerRefAttr>(namePath.back()))
349 return markAlive(hierPath);
352 dyn_cast_or_null<firrtl::InstanceOp>(innerRefNamespace->lookupOp(
353 cast<hw::InnerRefAttr>(namePath.drop_back().back()))))
354 instanceToHierPaths[instance].push_back(hierPath);
360 for (NamedAttribute namedAttr : op->getAttrs()) {
361 namedAttr.getValue().walk([&](Attribute subAttr) {
362 if (auto innerRef = dyn_cast<hw::InnerRefAttr>(subAttr))
363 if (auto instance = dyn_cast_or_null<firrtl::InstanceOp>(
364 innerRefNamespace->lookupOp(innerRef)))
367 if (auto flatSymbolRefAttr = dyn_cast<FlatSymbolRefAttr>(subAttr))
368 if (auto hierPath = symbolTable->template lookup<hw::HierPathOp>(
369 flatSymbolRefAttr.getAttr()))
378 SmallVector<FModuleOp, 0> modules(llvm::make_filter_range(
380 llvm::post_order(instanceGraph),
381 [](
auto *node) {
return dyn_cast<FModuleOp>(*node->getModule()); }),
382 [](
auto module) {
return module; }));
386 for (
auto module : modules)
387 forwardConstantOutputPort(module);
389 for (
auto module : circuit.getBodyBlock()->getOps<FModuleOp>()) {
391 if (module.isPublic()) {
392 markBlockExecutable(module.getBodyBlock());
393 for (
auto port : module.getBodyBlock()->getArguments())
399 auto visitAnnotation = [&](
int portId,
Annotation anno) ->
bool {
400 auto hierPathSym = anno.getMember<FlatSymbolRefAttr>(
"circt.nonlocal");
401 hw::HierPathOp hierPathOp;
404 symbolTable->template lookup<hw::HierPathOp>(hierPathSym.getAttr());
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 assert(isBlockExecutable(module.getBodyBlock()) &&
544 "unreachable modules must be already deleted");
546 auto removeDeadNonLocalAnnotations = [&](
int _,
Annotation anno) ->
bool {
547 auto hierPathSym = anno.getMember<FlatSymbolRefAttr>(
"circt.nonlocal");
551 symbolTable->template lookup<hw::HierPathOp>(hierPathSym.getAttr());
552 return !liveElements.count(hierPathOp);
555 AnnotationSet::removePortAnnotations(module, removeDeadNonLocalAnnotations);
556 AnnotationSet::removeAnnotations(
558 std::bind(removeDeadNonLocalAnnotations, -1, std::placeholders::_1));
561 module.walk<mlir::WalkOrder::PostOrder, mlir::ReverseIterator>(
564 LLVM_DEBUG(llvm::dbgs() <<
"Visit: " << *op <<
"\n");
565 if (
auto connect = dyn_cast<FConnectLike>(op)) {
566 if (isAssumedDead(
connect.getDest())) {
567 LLVM_DEBUG(llvm::dbgs() <<
"DEAD: " <<
connect <<
"\n";);
577 LLVM_DEBUG(llvm::dbgs() <<
"DEAD: " << *op <<
"\n";);
578 assert(op->use_empty() &&
"users should be already removed");
585 if (mlir::isOpTriviallyDead(op)) {
592 void IMDeadCodeElimPass::rewriteModuleSignature(FModuleOp module) {
593 assert(isBlockExecutable(module.getBodyBlock()) &&
594 "unreachable modules must be already deleted");
596 LLVM_DEBUG(llvm::dbgs() <<
"Prune ports of module: " << module.getName()
599 auto replaceInstanceResultWithWire = [&](ImplicitLocOpBuilder &builder,
601 InstanceOp instance) {
602 auto result = instance.getResult(index);
603 if (isAssumedDead(result)) {
607 .create<mlir::UnrealizedConversionCastOp>(
608 ArrayRef<Type>{result.getType()}, ArrayRef<Value>{})
610 result.replaceAllUsesWith(wire);
614 Value wire = builder.create<WireOp>(result.getType()).getResult();
615 result.replaceAllUsesWith(wire);
619 liveElements.erase(result);
620 liveElements.insert(wire);
624 for (
auto *use : llvm::make_early_inc_range(instanceGraphNode->
uses())) {
625 auto instance = cast<InstanceOp>(*use->getInstance());
626 if (!liveElements.count(instance)) {
628 ImplicitLocOpBuilder builder(instance.getLoc(), instance);
629 for (
auto index : llvm::seq(0u, instance.getNumResults()))
630 replaceInstanceResultWithWire(builder, index, instance);
638 if (module.isPublic())
641 unsigned numOldPorts = module.getNumPorts();
642 llvm::BitVector deadPortIndexes(numOldPorts);
644 ImplicitLocOpBuilder builder(module.getLoc(), module.getContext());
645 builder.setInsertionPointToStart(module.getBodyBlock());
646 auto oldPorts = module.getPorts();
648 for (
auto index : llvm::seq(0u, numOldPorts)) {
649 auto argument = module.getArgument(index);
651 "If the port has don't touch, it should be known alive");
657 if (isKnownAlive(argument)) {
661 if (module.getPortDirection(index) == Direction::In)
666 if (llvm::any_of(instanceGraph->lookup(module)->uses(),
669 record->getInstance()->getResult(index));
675 auto wire = builder.create<WireOp>(argument.getType()).getResult();
678 liveElements.erase(argument);
679 liveElements.insert(wire);
680 argument.replaceAllUsesWith(wire);
681 deadPortIndexes.set(index);
688 .create<mlir::UnrealizedConversionCastOp>(
689 ArrayRef<Type>{argument.getType()}, ArrayRef<Value>{})
692 argument.replaceAllUsesWith(wire);
693 assert(isAssumedDead(wire) &&
"dummy wire must be dead");
694 deadPortIndexes.set(index);
698 if (deadPortIndexes.none())
703 for (
auto arg : module.getArguments())
704 liveElements.erase(arg);
707 module.erasePorts(deadPortIndexes);
710 for (
auto arg : module.getArguments())
711 liveElements.insert(arg);
714 for (
auto *use : llvm::make_early_inc_range(instanceGraphNode->
uses())) {
715 auto instance = cast<InstanceOp>(*use->getInstance());
716 ImplicitLocOpBuilder builder(instance.getLoc(), instance);
718 for (
auto index : deadPortIndexes.set_bits())
719 replaceInstanceResultWithWire(builder, index, instance);
723 for (
auto oldResult : instance.getResults())
724 liveElements.erase(oldResult);
727 auto newInstance = instance.erasePorts(builder, deadPortIndexes);
730 for (
auto newResult : newInstance.getResults())
731 liveElements.insert(newResult);
733 instanceGraph->replaceInstance(instance, newInstance);
734 if (liveElements.contains(instance)) {
735 liveElements.erase(instance);
736 liveElements.insert(newInstance);
742 numRemovedPorts += deadPortIndexes.count();
745 void IMDeadCodeElimPass::eraseEmptyModule(FModuleOp module) {
747 if (!module.getBodyBlock()->empty())
751 if (module.isPublic()) {
752 mlir::emitWarning(module.getLoc())
753 <<
"module `" << module.getName()
754 <<
"` is empty but cannot be removed because the module is public";
758 if (!module.getAnnotations().empty()) {
759 module.emitWarning() <<
"module `" << module.getName()
760 <<
"` is empty but cannot be removed "
761 "because the module has annotations "
762 << module.getAnnotations();
766 if (!module.getBodyBlock()->args_empty()) {
767 auto diag = module.emitWarning()
768 <<
"module `" << module.getName()
769 <<
"` is empty but cannot be removed because the "
771 llvm::interleaveComma(module.getPortNames(), diag);
772 diag <<
" are referenced by name or dontTouched";
777 LLVM_DEBUG(llvm::dbgs() <<
"Erase " << module.getName() <<
"\n");
780 instanceGraph->lookup(module.getModuleNameAttr());
782 SmallVector<Location> instancesWithSymbols;
783 for (
auto *use : llvm::make_early_inc_range(instanceGraphNode->
uses())) {
784 auto instance = cast<InstanceOp>(use->getInstance());
785 if (instance.getInnerSym()) {
786 instancesWithSymbols.push_back(instance.getLoc());
794 if (!instancesWithSymbols.empty()) {
795 auto diag = module.emitWarning()
796 <<
"module `" << module.getName()
797 <<
"` is empty but cannot be removed because an instance is "
798 "referenced by name";
799 diag.attachNote(
FusedLoc::get(&getContext(), instancesWithSymbols))
800 <<
"these are instances with symbols";
804 instanceGraph->erase(instanceGraphNode);
810 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.
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.