16 #include "mlir/IR/ImplicitLocOpBuilder.h"
17 #include "mlir/IR/Threading.h"
18 #include "mlir/Interfaces/SideEffectInterfaces.h"
19 #include "llvm/ADT/BitVector.h"
20 #include "llvm/ADT/DenseMapInfoVariant.h"
21 #include "llvm/ADT/PostOrderIterator.h"
22 #include "llvm/ADT/TinyPtrVector.h"
23 #include "llvm/Support/Debug.h"
25 #define DEBUG_TYPE "firrtl-imdeadcodeelim"
27 using namespace circt;
28 using namespace firrtl;
32 return !(mlir::isMemoryEffectFree(op) ||
33 mlir::hasSingleEffect<mlir::MemoryEffects::Allocate>(op) ||
34 mlir::hasSingleEffect<mlir::MemoryEffects::Read>(op));
39 return isa<WireOp, RegResetOp, RegOp, NodeOp, MemOp>(op);
44 if (
auto name = dyn_cast<FNamableOp>(op))
45 if (!name.hasDroppableName())
51 struct IMDeadCodeElimPass :
public IMDeadCodeElimBase<IMDeadCodeElimPass> {
52 void runOnOperation()
override;
54 void rewriteModuleSignature(FModuleOp module);
55 void rewriteModuleBody(FModuleOp module);
56 void eraseEmptyModule(FModuleOp module);
57 void forwardConstantOutputPort(FModuleOp module);
60 bool isKnownAlive(Value value)
const {
61 assert(value &&
"null should not be used");
62 return liveElements.count(value);
66 bool isAssumedDead(Value value)
const {
return !isKnownAlive(value); }
67 bool isAssumedDead(Operation *op)
const {
68 return llvm::none_of(op->getResults(),
69 [&](Value value) { return isKnownAlive(value); });
73 bool isBlockExecutable(Block *block)
const {
74 return executableBlocks.count(block);
77 void visitUser(Operation *op);
78 void visitValue(Value value);
80 void visitConnect(FConnectLike
connect);
81 void visitSubelement(Operation *op);
82 void markBlockExecutable(Block *block);
83 void markBlockUndeletable(Operation *op) {
84 markAlive(op->getParentOfType<FModuleOp>());
87 void markDeclaration(Operation *op);
88 void markInstanceOp(InstanceOp instanceOp);
89 void markObjectOp(ObjectOp objectOp);
90 void markUnknownSideEffectOp(Operation *op);
91 void visitInstanceOp(InstanceOp instance);
92 void visitHierPathOp(hw::HierPathOp hierpath);
93 void visitModuleOp(FModuleOp module);
97 DenseSet<Block *> executableBlocks;
103 std::variant<Value, FModuleOp, InstanceOp, hw::HierPathOp>;
105 void markAlive(ElementType element) {
106 if (!liveElements.insert(element).second)
108 worklist.push_back(element);
113 SmallVector<ElementType, 64> worklist;
114 llvm::DenseSet<ElementType> liveElements;
118 DenseMap<InstanceOp, SmallVector<hw::HierPathOp>> instanceToHierPaths;
121 DenseMap<hw::HierPathOp, SetVector<ElementType>> hierPathToElements;
125 mlir::SymbolTable *symbolTable;
129 void IMDeadCodeElimPass::visitInstanceOp(InstanceOp instance) {
130 markBlockUndeletable(instance);
132 auto module = instance.getReferencedModule<FModuleOp>(*instanceGraph);
141 for (
auto hierPath : instanceToHierPaths[instance])
145 for (
auto &blockArg : module.getBody().getArguments()) {
146 auto portNo = blockArg.getArgNumber();
148 isKnownAlive(module.getArgument(portNo)))
149 markAlive(instance.getResult(portNo));
153 void IMDeadCodeElimPass::visitModuleOp(FModuleOp module) {
155 for (
auto *use : instanceGraph->lookup(module)->uses())
156 markAlive(cast<InstanceOp>(*use->getInstance()));
159 void IMDeadCodeElimPass::visitHierPathOp(hw::HierPathOp hierPathOp) {
161 for (
auto path : hierPathOp.getNamepathAttr())
162 if (
auto innerRef = dyn_cast<hw::InnerRefAttr>(path)) {
163 auto *op = innerRefNamespace->lookupOp(innerRef);
164 if (
auto instance = dyn_cast_or_null<InstanceOp>(op))
168 for (
auto elem : hierPathToElements[hierPathOp])
172 void IMDeadCodeElimPass::markDeclaration(Operation *op) {
175 for (
auto result : op->getResults())
177 markBlockUndeletable(op);
181 void IMDeadCodeElimPass::markUnknownSideEffectOp(Operation *op) {
184 for (
auto result : op->getResults())
186 for (
auto operand : op->getOperands())
188 markBlockUndeletable(op);
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);
199 void IMDeadCodeElimPass::markInstanceOp(InstanceOp instance) {
201 Operation *op = instance.getReferencedModule(*instanceGraph);
205 if (!isa<FModuleOp>(op)) {
206 auto module = dyn_cast<FModuleLike>(op);
207 for (
auto resultNo : llvm::seq(0u, instance.getNumResults())) {
213 markAlive(instance.getResult(resultNo));
221 auto fModule = cast<FModuleOp>(op);
222 markBlockExecutable(fModule.getBodyBlock());
225 void IMDeadCodeElimPass::markObjectOp(ObjectOp
object) {
230 void IMDeadCodeElimPass::markBlockExecutable(Block *block) {
231 if (!executableBlocks.insert(block).second)
234 auto fmodule = cast<FModuleOp>(block->getParentOp());
235 if (fmodule.isPublic())
239 for (
auto blockArg : block->getArguments())
245 for (
auto &op : *block) {
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))
256 markUnknownSideEffectOp(&op);
262 void IMDeadCodeElimPass::forwardConstantOutputPort(FModuleOp module) {
264 SmallVector<std::pair<unsigned, APSInt>> constantPortIndicesAndValues;
265 auto ports = module.getPorts();
266 auto *instanceGraphNode = instanceGraph->lookup(module);
268 for (
const auto &e : llvm::enumerate(ports)) {
269 unsigned index = e.index();
270 auto port = e.value();
271 auto arg = module.getArgument(index);
279 if (
auto constant =
connect.getSrc().getDefiningOp<ConstantOp>())
280 constantPortIndicesAndValues.push_back({index, constant.getValue()});
284 if (constantPortIndicesAndValues.empty())
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");
296 result.replaceAllUsesWith(
builder.create<ConstantOp>(constant));
301 void IMDeadCodeElimPass::runOnOperation() {
303 auto circuits = getOperation().getOps<CircuitOp>();
304 if (circuits.empty())
307 auto circuit = *circuits.begin();
309 if (!llvm::hasSingleElement(circuits)) {
310 mlir::emitError(circuit.getLoc(),
311 "cannot process multiple circuit operations")
312 .attachNote((*std::next(circuits.begin())).getLoc())
313 <<
"second circuit here";
314 return signalPassFailure();
317 instanceGraph = &getChildAnalysis<InstanceGraph>(circuit);
318 symbolTable = &getChildAnalysis<SymbolTable>(circuit);
319 auto &istc = getChildAnalysis<hw::InnerSymbolTableCollection>(circuit);
322 innerRefNamespace = &theInnerRefNamespace;
325 getOperation().walk([&](Operation *op) {
326 if (isa<FModuleOp>(op))
329 if (
auto hierPath = dyn_cast<hw::HierPathOp>(op)) {
330 auto namePath = hierPath.getNamepath().getValue();
333 if (hierPath.isPublic() || namePath.size() <= 1 ||
334 isa<hw::InnerRefAttr>(namePath.back()))
335 return markAlive(hierPath);
338 dyn_cast_or_null<firrtl::InstanceOp>(innerRefNamespace->lookupOp(
339 cast<hw::InnerRefAttr>(namePath.drop_back().back()))))
340 instanceToHierPaths[instance].push_back(hierPath);
346 for (NamedAttribute namedAttr : op->getAttrs()) {
347 namedAttr.getValue().walk([&](Attribute subAttr) {
348 if (auto innerRef = dyn_cast<hw::InnerRefAttr>(subAttr))
349 if (auto instance = dyn_cast_or_null<firrtl::InstanceOp>(
350 innerRefNamespace->lookupOp(innerRef)))
353 if (auto flatSymbolRefAttr = dyn_cast<FlatSymbolRefAttr>(subAttr))
354 if (auto hierPath = symbolTable->template lookup<hw::HierPathOp>(
355 flatSymbolRefAttr.getAttr()))
364 SmallVector<FModuleOp, 0> modules(llvm::make_filter_range(
366 llvm::post_order(instanceGraph),
367 [](
auto *node) {
return dyn_cast<FModuleOp>(*node->getModule()); }),
368 [](
auto module) {
return module; }));
372 for (
auto module : modules)
373 forwardConstantOutputPort(module);
375 for (
auto module : circuit.getBodyBlock()->getOps<FModuleOp>()) {
377 if (module.isPublic()) {
378 markBlockExecutable(module.getBodyBlock());
379 for (
auto port : module.getBodyBlock()->getArguments())
385 auto visitAnnotation = [&](
int portId,
Annotation anno) ->
bool {
386 auto hierPathSym = anno.getMember<FlatSymbolRefAttr>(
"circt.nonlocal");
387 hw::HierPathOp hierPathOp;
390 symbolTable->template lookup<hw::HierPathOp>(hierPathSym.getAttr());
392 if (anno.canBeDeleted()) {
393 if (hierPathOp && portId >= 0)
394 hierPathToElements[hierPathOp].insert(module.getArgument(portId));
398 markAlive(hierPathOp);
400 markAlive(module.getArgument(portId));
407 module, std::bind(visitAnnotation, -1, std::placeholders::_1));
411 while (!worklist.empty()) {
412 auto v = worklist.pop_back_val();
413 if (
auto *value = std::get_if<Value>(&v))
415 else if (
auto *instance = std::get_if<InstanceOp>(&v))
416 visitInstanceOp(*instance);
417 else if (
auto *hierpath = std::get_if<hw::HierPathOp>(&v))
418 visitHierPathOp(*hierpath);
419 else if (
auto *module = std::get_if<FModuleOp>(&v))
420 visitModuleOp(*module);
424 for (
auto module : llvm::make_early_inc_range(
425 circuit.getBodyBlock()->getOps<FModuleOp>())) {
426 if (isBlockExecutable(module.getBodyBlock()))
427 rewriteModuleSignature(module);
438 mlir::parallelForEach(circuit.getContext(),
439 circuit.getBodyBlock()->getOps<FModuleOp>(),
440 [&](
auto op) { rewriteModuleBody(op); });
443 for (
auto op : llvm::make_early_inc_range(
444 circuit.getBodyBlock()->getOps<hw::HierPathOp>()))
445 if (!liveElements.count(op))
448 for (
auto module : modules)
449 eraseEmptyModule(module);
452 executableBlocks.clear();
453 liveElements.clear();
454 instanceToHierPaths.clear();
455 hierPathToElements.clear();
458 void IMDeadCodeElimPass::visitValue(Value value) {
459 assert(isKnownAlive(value) &&
"only alive values reach here");
462 for (Operation *user : value.getUsers())
466 if (
auto blockArg = dyn_cast<BlockArgument>(value)) {
467 auto module = cast<FModuleOp>(blockArg.getParentBlock()->getParentOp());
468 auto portDirection = module.getPortDirection(blockArg.getArgNumber());
472 if (portDirection == Direction::In) {
473 for (
auto *instRec : instanceGraph->lookup(module)->uses()) {
474 auto instance = cast<InstanceOp>(instRec->getInstance());
475 if (liveElements.contains(instance))
476 markAlive(instance.getResult(blockArg.getArgNumber()));
484 if (
auto instance = value.getDefiningOp<InstanceOp>()) {
485 auto instanceResult = cast<mlir::OpResult>(value);
487 auto module = instance.getReferencedModule<FModuleOp>(*instanceGraph);
490 if (!module || module.getPortDirection(instanceResult.getResultNumber()) ==
496 BlockArgument modulePortVal =
497 module.getArgument(instanceResult.getResultNumber());
498 return markAlive(modulePortVal);
502 if (
auto mem = value.getDefiningOp<MemOp>()) {
503 for (
auto port : mem->getResults())
509 if (
auto op = value.getDefiningOp())
510 for (
auto operand : op->getOperands())
514 if (
auto fop = value.getDefiningOp<Forceable>();
515 fop && fop.isForceable() &&
516 (fop.getData() == value || fop.getDataRef() == value)) {
517 markAlive(fop.getData());
518 markAlive(fop.getDataRef());
522 void IMDeadCodeElimPass::visitConnect(FConnectLike
connect) {
524 if (isKnownAlive(
connect.getDest()))
528 void IMDeadCodeElimPass::visitSubelement(Operation *op) {
529 if (isKnownAlive(op->getOperand(0)))
530 markAlive(op->getResult(0));
533 void IMDeadCodeElimPass::rewriteModuleBody(FModuleOp module) {
534 auto *body = module.getBodyBlock();
535 assert(isBlockExecutable(body) &&
536 "unreachable modules must be already deleted");
538 auto removeDeadNonLocalAnnotations = [&](
int _,
Annotation anno) ->
bool {
539 auto hierPathSym = anno.getMember<FlatSymbolRefAttr>(
"circt.nonlocal");
542 if (!anno.canBeDeleted() || !hierPathSym)
545 symbolTable->template lookup<hw::HierPathOp>(hierPathSym.getAttr());
546 return !liveElements.count(hierPathOp);
549 AnnotationSet::removePortAnnotations(module, removeDeadNonLocalAnnotations);
550 AnnotationSet::removeAnnotations(
552 std::bind(removeDeadNonLocalAnnotations, -1, std::placeholders::_1));
555 for (
auto &op : llvm::make_early_inc_range(llvm::reverse(*body))) {
557 if (
auto connect = dyn_cast<FConnectLike>(op)) {
558 if (isAssumedDead(
connect.getDest())) {
559 LLVM_DEBUG(llvm::dbgs() <<
"DEAD: " <<
connect <<
"\n";);
568 isAssumedDead(&op)) {
569 LLVM_DEBUG(llvm::dbgs() <<
"DEAD: " << op <<
"\n";);
570 assert(op.use_empty() &&
"users should be already removed");
577 if (mlir::isOpTriviallyDead(&op)) {
584 void IMDeadCodeElimPass::rewriteModuleSignature(FModuleOp module) {
585 assert(isBlockExecutable(module.getBodyBlock()) &&
586 "unreachable modules must be already deleted");
588 LLVM_DEBUG(llvm::dbgs() <<
"Prune ports of module: " << module.getName()
591 auto replaceInstanceResultWithWire = [&](ImplicitLocOpBuilder &
builder,
593 InstanceOp instance) {
594 auto result = instance.getResult(index);
595 if (isAssumedDead(result)) {
599 .create<mlir::UnrealizedConversionCastOp>(
600 ArrayRef<Type>{result.getType()}, ArrayRef<Value>{})
602 result.replaceAllUsesWith(wire);
606 Value wire =
builder.create<WireOp>(result.getType()).getResult();
607 result.replaceAllUsesWith(wire);
611 liveElements.erase(result);
612 liveElements.insert(wire);
616 for (
auto *use : llvm::make_early_inc_range(instanceGraphNode->
uses())) {
617 auto instance = cast<InstanceOp>(*use->getInstance());
618 if (!liveElements.count(instance)) {
620 ImplicitLocOpBuilder
builder(instance.getLoc(), instance);
621 for (
auto index : llvm::seq(0u, instance.getNumResults()))
622 replaceInstanceResultWithWire(
builder, index, instance);
630 if (module.isPublic())
633 unsigned numOldPorts = module.getNumPorts();
634 llvm::BitVector deadPortIndexes(numOldPorts);
636 ImplicitLocOpBuilder
builder(module.getLoc(), module.getContext());
637 builder.setInsertionPointToStart(module.getBodyBlock());
638 auto oldPorts = module.getPorts();
640 for (
auto index : llvm::seq(0u, numOldPorts)) {
641 auto argument = module.getArgument(index);
643 "If the port has don't touch, it should be known alive");
649 if (isKnownAlive(argument)) {
653 if (module.getPortDirection(index) == Direction::In)
658 if (llvm::any_of(instanceGraph->lookup(module)->uses(),
661 record->getInstance()->getResult(index));
667 auto wire =
builder.create<WireOp>(argument.getType()).getResult();
670 liveElements.erase(argument);
671 liveElements.insert(wire);
672 argument.replaceAllUsesWith(wire);
673 deadPortIndexes.set(index);
680 .create<mlir::UnrealizedConversionCastOp>(
681 ArrayRef<Type>{argument.getType()}, ArrayRef<Value>{})
684 argument.replaceAllUsesWith(wire);
685 assert(isAssumedDead(wire) &&
"dummy wire must be dead");
686 deadPortIndexes.set(index);
690 if (deadPortIndexes.none())
695 for (
auto arg : module.getArguments())
696 liveElements.erase(arg);
699 module.erasePorts(deadPortIndexes);
702 for (
auto arg : module.getArguments())
703 liveElements.insert(arg);
706 for (
auto *use : llvm::make_early_inc_range(instanceGraphNode->
uses())) {
707 auto instance = cast<InstanceOp>(*use->getInstance());
708 ImplicitLocOpBuilder
builder(instance.getLoc(), instance);
710 for (
auto index : deadPortIndexes.set_bits())
711 replaceInstanceResultWithWire(
builder, index, instance);
715 for (
auto oldResult : instance.getResults())
716 liveElements.erase(oldResult);
719 auto newInstance = instance.erasePorts(
builder, deadPortIndexes);
722 for (
auto newResult : newInstance.getResults())
723 liveElements.insert(newResult);
725 instanceGraph->replaceInstance(instance, newInstance);
726 if (liveElements.contains(instance)) {
727 liveElements.erase(instance);
728 liveElements.insert(newInstance);
734 numRemovedPorts += deadPortIndexes.count();
737 void IMDeadCodeElimPass::eraseEmptyModule(FModuleOp module) {
739 if (!module.getBodyBlock()->empty())
743 if (module.isPublic()) {
744 mlir::emitWarning(module.getLoc())
745 <<
"module `" << module.getName()
746 <<
"` is empty but cannot be removed because the module is public";
750 if (!module.getAnnotations().empty()) {
751 module.emitWarning() <<
"module `" << module.getName()
752 <<
"` is empty but cannot be removed "
753 "because the module has annotations "
754 << module.getAnnotations();
758 if (!module.getBodyBlock()->args_empty()) {
759 auto diag = module.emitWarning()
760 <<
"module `" << module.getName()
761 <<
"` is empty but cannot be removed because the "
763 llvm::interleaveComma(module.getPortNames(), diag);
764 diag <<
" are referenced by name or dontTouched";
769 LLVM_DEBUG(llvm::dbgs() <<
"Erase " << module.getName() <<
"\n");
772 instanceGraph->lookup(module.getModuleNameAttr());
774 SmallVector<Location> instancesWithSymbols;
775 for (
auto *use : llvm::make_early_inc_range(instanceGraphNode->
uses())) {
776 auto instance = cast<InstanceOp>(use->getInstance());
777 if (instance.getInnerSym()) {
778 instancesWithSymbols.push_back(instance.getLoc());
786 if (!instancesWithSymbols.empty()) {
787 auto diag = module.emitWarning()
788 <<
"module `" << module.getName()
789 <<
"` is empty but cannot be removed because an instance is "
790 "referenced by name";
791 diag.attachNote(
FusedLoc::get(&getContext(), instancesWithSymbols))
792 <<
"these are instances with symbols";
796 instanceGraph->erase(instanceGraphNode);
802 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()
StrictConnectOp 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.