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"
24 #define DEBUG_TYPE "firrtl-imdeadcodeelim"
26 using namespace circt;
27 using namespace firrtl;
31 return !(mlir::isMemoryEffectFree(op) ||
32 mlir::hasSingleEffect<mlir::MemoryEffects::Allocate>(op) ||
33 mlir::hasSingleEffect<mlir::MemoryEffects::Read>(op));
38 return isa<WireOp, RegResetOp, RegOp, NodeOp, MemOp>(op);
43 if (
auto name = dyn_cast<FNamableOp>(op))
44 if (!name.hasDroppableName())
50 struct IMDeadCodeElimPass :
public IMDeadCodeElimBase<IMDeadCodeElimPass> {
51 void runOnOperation()
override;
53 void rewriteModuleSignature(FModuleOp module);
54 void rewriteModuleBody(FModuleOp module);
55 void eraseEmptyModule(FModuleOp module);
56 void forwardConstantOutputPort(FModuleOp module);
59 bool isKnownAlive(Value
value)
const {
61 return liveElements.count(
value);
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); });
72 bool isBlockExecutable(Block *block)
const {
73 return executableBlocks.count(block);
76 void visitUser(Operation *op);
77 void visitValue(Value
value);
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>());
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);
96 DenseSet<Block *> executableBlocks;
102 std::variant<Value, FModuleOp, InstanceOp, hw::HierPathOp>;
104 void markAlive(ElementType element) {
105 if (!liveElements.insert(element).second)
107 worklist.push_back(element);
112 SmallVector<ElementType, 64> worklist;
113 llvm::DenseSet<ElementType> liveElements;
117 DenseMap<InstanceOp, SmallVector<hw::HierPathOp>> instanceToHierPaths;
120 DenseMap<hw::HierPathOp, SetVector<ElementType>> hierPathToElements;
124 mlir::SymbolTable *symbolTable;
128 void IMDeadCodeElimPass::visitInstanceOp(InstanceOp instance) {
129 markBlockUndeletable(instance);
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 = path.dyn_cast<hw::InnerRefAttr>()) {
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) {
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 llvm::dbgs() <<
"===----- Inter-module Dead Code Elimination -----==="
305 auto circuits = getOperation().getOps<CircuitOp>();
306 if (circuits.empty())
309 auto circuit = *circuits.begin();
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();
319 instanceGraph = &getChildAnalysis<InstanceGraph>(circuit);
320 symbolTable = &getChildAnalysis<SymbolTable>(circuit);
321 auto &istc = getChildAnalysis<hw::InnerSymbolTableCollection>(circuit);
324 innerRefNamespace = &theInnerRefNamespace;
327 getOperation().walk([&](Operation *op) {
328 if (isa<FModuleOp>(op))
331 if (
auto hierPath = dyn_cast<hw::HierPathOp>(op)) {
332 auto namePath = hierPath.getNamepath().getValue();
335 if (hierPath.isPublic() || namePath.size() <= 1 ||
336 namePath.back().isa<hw::InnerRefAttr>())
337 return markAlive(hierPath);
340 dyn_cast_or_null<firrtl::InstanceOp>(innerRefNamespace->lookupOp(
341 namePath.drop_back().back().cast<hw::InnerRefAttr>())))
342 instanceToHierPaths[instance].push_back(hierPath);
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)))
355 if (auto flatSymbolRefAttr = dyn_cast<FlatSymbolRefAttr>(subAttr))
356 if (auto hierPath = symbolTable->template lookup<hw::HierPathOp>(
357 flatSymbolRefAttr.getAttr()))
366 SmallVector<FModuleOp, 0> modules(llvm::make_filter_range(
368 llvm::post_order(instanceGraph),
369 [](
auto *node) {
return dyn_cast<FModuleOp>(*node->getModule()); }),
370 [](
auto module) {
return module; }));
374 for (
auto module : modules)
375 forwardConstantOutputPort(module);
377 for (
auto module : circuit.getBodyBlock()->getOps<FModuleOp>()) {
379 if (module.isPublic()) {
380 markBlockExecutable(module.getBodyBlock());
381 for (
auto port : module.getBodyBlock()->getArguments())
387 auto visitAnnotation = [&](
int portId,
Annotation anno) ->
bool {
388 auto hierPathSym = anno.getMember<FlatSymbolRefAttr>(
"circt.nonlocal");
389 hw::HierPathOp hierPathOp;
392 symbolTable->template lookup<hw::HierPathOp>(hierPathSym.getAttr());
394 if (anno.canBeDeleted()) {
395 if (hierPathOp && portId >= 0)
396 hierPathToElements[hierPathOp].insert(module.getArgument(portId));
400 markAlive(hierPathOp);
402 markAlive(module.getArgument(portId));
409 module, std::bind(visitAnnotation, -1, std::placeholders::_1));
413 while (!worklist.empty()) {
414 auto v = worklist.pop_back_val();
415 if (
auto *
value = std::get_if<Value>(&v))
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);
426 for (
auto module : llvm::make_early_inc_range(
427 circuit.getBodyBlock()->getOps<FModuleOp>())) {
428 if (isBlockExecutable(module.getBodyBlock()))
429 rewriteModuleSignature(module);
440 mlir::parallelForEach(circuit.getContext(),
441 circuit.getBodyBlock()->getOps<FModuleOp>(),
442 [&](
auto op) { rewriteModuleBody(op); });
445 for (
auto op : llvm::make_early_inc_range(
446 circuit.getBodyBlock()->getOps<hw::HierPathOp>()))
447 if (!liveElements.count(op))
450 for (
auto module : modules)
451 if (module != circuit.getMainModule())
452 eraseEmptyModule(module);
455 executableBlocks.clear();
456 liveElements.clear();
457 instanceToHierPaths.clear();
458 hierPathToElements.clear();
461 void IMDeadCodeElimPass::visitValue(Value
value) {
462 assert(isKnownAlive(
value) &&
"only alive values reach here");
465 for (Operation *user :
value.getUsers())
469 if (
auto blockArg = dyn_cast<BlockArgument>(
value)) {
470 auto module = cast<FModuleOp>(blockArg.getParentBlock()->getParentOp());
471 auto portDirection = module.getPortDirection(blockArg.getArgNumber());
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()));
487 if (
auto instance =
value.getDefiningOp<InstanceOp>()) {
488 auto instanceResult =
value.cast<mlir::OpResult>();
494 if (!module || module.getPortDirection(instanceResult.getResultNumber()) ==
500 BlockArgument modulePortVal =
501 module.getArgument(instanceResult.getResultNumber());
502 return markAlive(modulePortVal);
506 if (
auto mem =
value.getDefiningOp<MemOp>()) {
507 for (
auto port : mem->getResults())
513 if (
auto op =
value.getDefiningOp())
514 for (
auto operand : op->getOperands())
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());
526 void IMDeadCodeElimPass::visitConnect(FConnectLike
connect) {
528 if (isKnownAlive(
connect.getDest()))
532 void IMDeadCodeElimPass::visitSubelement(Operation *op) {
533 if (isKnownAlive(op->getOperand(0)))
534 markAlive(op->getResult(0));
537 void IMDeadCodeElimPass::rewriteModuleBody(FModuleOp module) {
538 auto *body = module.getBodyBlock();
539 assert(isBlockExecutable(body) &&
540 "unreachable modules must be already deleted");
542 auto removeDeadNonLocalAnnotations = [&](
int _,
Annotation anno) ->
bool {
543 auto hierPathSym = anno.getMember<FlatSymbolRefAttr>(
"circt.nonlocal");
546 if (!anno.canBeDeleted() || !hierPathSym)
549 symbolTable->template lookup<hw::HierPathOp>(hierPathSym.getAttr());
550 return !liveElements.count(hierPathOp);
553 AnnotationSet::removePortAnnotations(module, removeDeadNonLocalAnnotations);
554 AnnotationSet::removeAnnotations(
556 std::bind(removeDeadNonLocalAnnotations, -1, std::placeholders::_1));
559 for (
auto &op : llvm::make_early_inc_range(llvm::reverse(*body))) {
561 if (
auto connect = dyn_cast<FConnectLike>(op)) {
562 if (isAssumedDead(
connect.getDest())) {
572 isAssumedDead(&op)) {
573 LLVM_DEBUG(
llvm::dbgs() <<
"DEAD: " << op <<
"\n";);
574 assert(op.use_empty() &&
"users should be already removed");
581 if (mlir::isOpTriviallyDead(&op)) {
588 void IMDeadCodeElimPass::rewriteModuleSignature(FModuleOp module) {
589 assert(isBlockExecutable(module.getBodyBlock()) &&
590 "unreachable modules must be already deleted");
592 LLVM_DEBUG(
llvm::dbgs() <<
"Prune ports of module: " << module.getName()
595 auto replaceInstanceResultWithWire = [&](ImplicitLocOpBuilder &
builder,
597 InstanceOp instance) {
598 auto result = instance.getResult(index);
599 if (isAssumedDead(result)) {
603 .create<mlir::UnrealizedConversionCastOp>(
604 ArrayRef<Type>{result.getType()}, ArrayRef<Value>{})
606 result.replaceAllUsesWith(wire);
610 Value wire =
builder.create<WireOp>(result.getType()).getResult();
611 result.replaceAllUsesWith(wire);
615 liveElements.erase(result);
616 liveElements.insert(wire);
620 for (
auto *use : llvm::make_early_inc_range(instanceGraphNode->
uses())) {
621 auto instance = cast<InstanceOp>(*use->getInstance());
622 if (!liveElements.count(instance)) {
624 ImplicitLocOpBuilder
builder(instance.getLoc(), instance);
625 for (
auto index : llvm::seq(0u, instance.getNumResults()))
626 replaceInstanceResultWithWire(
builder, index, instance);
634 if (module.isPublic())
637 unsigned numOldPorts = module.getNumPorts();
638 llvm::BitVector deadPortIndexes(numOldPorts);
640 ImplicitLocOpBuilder
builder(module.getLoc(), module.getContext());
641 builder.setInsertionPointToStart(module.getBodyBlock());
642 auto oldPorts = module.getPorts();
644 for (
auto index : llvm::seq(0u, numOldPorts)) {
645 auto argument = module.getArgument(index);
647 "If the port has don't touch, it should be known alive");
653 if (isKnownAlive(argument)) {
657 if (module.getPortDirection(index) == Direction::In)
662 if (llvm::any_of(instanceGraph->
lookup(module)->
uses(),
665 record->getInstance()->getResult(index));
671 auto wire =
builder.create<WireOp>(argument.getType()).getResult();
674 liveElements.erase(argument);
675 liveElements.insert(wire);
676 argument.replaceAllUsesWith(wire);
677 deadPortIndexes.set(index);
684 .create<mlir::UnrealizedConversionCastOp>(
685 ArrayRef<Type>{argument.getType()}, ArrayRef<Value>{})
688 argument.replaceAllUsesWith(wire);
689 assert(isAssumedDead(wire) &&
"dummy wire must be dead");
690 deadPortIndexes.set(index);
694 if (deadPortIndexes.none())
699 for (
auto arg : module.getArguments())
700 liveElements.erase(arg);
703 module.erasePorts(deadPortIndexes);
706 for (
auto arg : module.getArguments())
707 liveElements.insert(arg);
710 for (
auto *use : llvm::make_early_inc_range(instanceGraphNode->
uses())) {
711 auto instance = cast<InstanceOp>(*use->getInstance());
712 ImplicitLocOpBuilder
builder(instance.getLoc(), instance);
714 for (
auto index : deadPortIndexes.set_bits())
715 replaceInstanceResultWithWire(
builder, index, instance);
719 for (
auto oldResult : instance.getResults())
720 liveElements.erase(oldResult);
723 auto newInstance = instance.erasePorts(
builder, deadPortIndexes);
726 for (
auto newResult : newInstance.getResults())
727 liveElements.insert(newResult);
730 if (liveElements.contains(instance)) {
731 liveElements.erase(instance);
732 liveElements.insert(newInstance);
738 numRemovedPorts += deadPortIndexes.count();
741 void IMDeadCodeElimPass::eraseEmptyModule(FModuleOp module) {
743 if (!module.getBodyBlock()->empty())
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";
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();
762 if (!module.getBodyBlock()->args_empty()) {
763 auto diag = module.emitWarning()
764 <<
"module `" << module.getName()
765 <<
"` is empty but cannot be removed because the "
767 llvm::interleaveComma(module.getPortNames(), diag);
768 diag <<
" are referenced by name or dontTouched";
773 LLVM_DEBUG(
llvm::dbgs() <<
"Erase " << module.getName() <<
"\n");
776 instanceGraph->
lookup(module.getModuleNameAttr());
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());
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";
800 instanceGraph->
erase(instanceGraphNode);
806 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()
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.
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...
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
mlir::raw_indented_ostream & dbgs()
This class represents the namespace in which InnerRef's can be resolved.