[FIRRTL] Segfault in Dedup Pass

Platform: macOS 12.4, x86_64 circt commit: be20cdeebf9fcc3c0ca249f89c8913778a3d94f6

Hey all, I'm trying to run firtool on the FIRRTL output of a Chisel-based design from my company (which unfortunately means I can't provide the input .fir file), and running into a segfault during the DedupPass. The stacktrace follows:

$ ./build/bin/firtool --format=fir --warn-on-unprocessed-annotations --verify-each=false --dedup=1 --annotation-file=MyDesign.anno.json -o MyDesign.v MyDesign.fir --verbose-pass-executions
[firtool] Running fir parser
[firtool] -- Done in 5.432 sec
[firtool] Running "firrtl.circuit(firrtl-lower-annotations{disable-annotation-classless=false disable-annotation-unknown=true},firrtl.module(cse),firrtl-inject-dut-hier,firrtl.module(firrtl-lower-chirrtl),firrtl-infer-widths,firrtl-mem-to-reg-of-vec{ignore-read-enable-mem=false repl-seq-mem=false},firrtl-infer-resets,firrtl-dedup,firrtl-dft,firrtl-lower-types{flatten-mem=false preserve-aggregate=false preserve-public-types=true},firrtl.module(firrtl-expand-whens,firrtl-sfc-compat,canonicalize{  max-iterations=10 region-simplify=false top-down=true},firrtl-infer-rw),firrtl-prefix-modules,firrtl-inliner,firrtl-imconstprop,firrtl-add-seqmem-ports,firrtl-emit-metadata{repl-seq-mem=false repl-seq-mem-circuit= repl-seq-mem-file=},firrtl-extract-instances,firrtl-blackbox-reader{input-prefix=MyDesign},firrtl.module(canonicalize{  max-iterations=10 region-simplify=false top-down=true}),firrtl-remove-unused-ports,firrtl-emit-omir{file=})"
[firtool]   Running "firrtl-lower-annotations{disable-annotation-classless=false disable-annotation-unknown=true}"
[firtool]   -- Done in 0.000 sec
[firtool]   Running "firrtl.module(cse)"
[firtool]   -- Done in 1.493 sec
[firtool]   Running "firrtl-inject-dut-hier"
[firtool]   -- Done in 0.000 sec
[firtool]   Running "firrtl.module(firrtl-lower-chirrtl)"
[firtool]   -- Done in 0.569 sec
[firtool]   Running "firrtl-infer-widths"
[firtool]   -- Done in 0.692 sec
[firtool]   Running "firrtl-mem-to-reg-of-vec{ignore-read-enable-mem=false repl-seq-mem=false}"
[firtool]   -- Done in 0.000 sec
[firtool]   Running "firrtl-infer-resets"
[firtool]   -- Done in 1.357 sec
[firtool]   Running "firrtl-dedup"
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.  Program arguments: ./build/bin/firtool --format=fir --warn-on-unprocessed-annotations --verify-each=false --dedup=1 --annotation-file=MyDesign.anno.json -o MyDesign.v MyDesign.fir --verbose-pass-executions
Stack dump without symbol names (ensure you have llvm-symbolizer in your PATH or set the environment var `LLVM_SYMBOLIZER_PATH` to point to it):
0  firtool                  0x000000010a363ecd llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) + 61
1  firtool                  0x000000010a36444b PrintStackTraceSignalHandler(void*) + 27
2  firtool                  0x000000010a362136 llvm::sys::RunSignalHandlers() + 134
3  firtool                  0x000000010a36609f SignalHandler(int) + 223
4  libsystem_platform.dylib 0x00007ff8117cadfd _sigtramp + 29
5  libsystem_platform.dylib 0x00007ff7b5d8ce58 _sigtramp + 18446744072172085368
6  firtool                  0x000000010a866df5 llvm::ilist_node_impl<llvm::ilist_detail::node_options<circt::hw::InstanceRecord, true, false, void>>::getNext() + 21
7  firtool                  0x000000010a866dcc llvm::ilist_iterator<llvm::ilist_detail::node_options<circt::hw::InstanceRecord, true, false, void>, false, false>::operator++() + 28
8  firtool                  0x000000010a5a6ae9 llvm::iterator_adaptor_base<llvm::mapped_iterator<llvm::ilist_iterator<llvm::ilist_detail::node_options<circt::hw::InstanceRecord, true, false, void>, false, false>, circt::hw::InstanceRecord* (*)(circt::hw::InstanceRecord&), circt::hw::InstanceRecord*>, llvm::ilist_iterator<llvm::ilist_detail::node_options<circt::hw::InstanceRecord, true, false, void>, false, false>, std::__1::bidirectional_iterator_tag, circt::hw::InstanceRecord*, long, circt::hw::InstanceRecord**, circt::hw::InstanceRecord*>::operator++() + 25
9  firtool                  0x000000010a5a6ab9 llvm::iterator_adaptor_base<llvm::mapped_iterator<circt::hw::detail::AddressIterator<llvm::ilist_iterator<llvm::ilist_detail::node_options<circt::hw::InstanceRecord, true, false, void>, false, false>>, circt::hw::InstanceGraphNode* (*)(circt::hw::InstanceRecord const*), circt::hw::InstanceGraphNode*>, circt::hw::detail::AddressIterator<llvm::ilist_iterator<llvm::ilist_detail::node_options<circt::hw::InstanceRecord, true, false, void>, false, false>>, std::__1::bidirectional_iterator_tag, circt::hw::InstanceGraphNode*, long, circt::hw::InstanceGraphNode**, circt::hw::InstanceGraphNode*>::operator++() + 25
10 firtool                  0x000000010a5a6958 llvm::iterator_facade_base<llvm::mapped_iterator<circt::hw::detail::AddressIterator<llvm::ilist_iterator<llvm::ilist_detail::node_options<circt::hw::InstanceRecord, true, false, void>, false, false>>, circt::hw::InstanceGraphNode* (*)(circt::hw::InstanceRecord const*), circt::hw::InstanceGraphNode*>, std::__1::bidirectional_iterator_tag, circt::hw::InstanceGraphNode*, long, circt::hw::InstanceGraphNode**, circt::hw::InstanceGraphNode*>::operator++(int) + 56
11 firtool                  0x000000010a5a5b60 llvm::po_iterator<circt::firrtl::InstanceGraph*, llvm::SmallPtrSet<circt::hw::InstanceGraphNode*, 8u>, false, llvm::GraphTraits<circt::firrtl::InstanceGraph*>>::traverseChild() + 144
12 firtool                  0x000000010a59fe9b llvm::po_iterator<circt::firrtl::InstanceGraph*, llvm::SmallPtrSet<circt::hw::InstanceGraphNode*, 8u>, false, llvm::GraphTraits<circt::firrtl::InstanceGraph*>>::operator++() + 91
13 firtool                  0x000000010a59e39d (anonymous namespace)::DedupPass::runOnOperation() + 1197
14 firtool                  0x000000010b27855c mlir::detail::OpToOpPassAdaptor::run(mlir::Pass*, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int) + 620
15 firtool                  0x000000010b278d26 mlir::detail::OpToOpPassAdaptor::runPipeline(mlir::OpPassManager&, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int, mlir::PassInstrumentor*, mlir::PassInstrumentation::PipelineParentInfo const*) + 390
16 firtool                  0x000000010b28e418 mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::$_12::operator()(mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::OpPMInfo&) const + 232
17 firtool                  0x000000010b28e0a9 mlir::LogicalResult mlir::failableParallelForEach<std::__1::__wrap_iter<mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::OpPMInfo*>, mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::$_12&>(mlir::MLIRContext*, std::__1::__wrap_iter<mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::OpPMInfo*>, std::__1::__wrap_iter<mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::OpPMInfo*>, mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::$_12&) + 185
18 firtool                  0x000000010b27a9e3 mlir::LogicalResult mlir::failableParallelForEach<std::__1::vector<mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::OpPMInfo, std::__1::allocator<mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::OpPMInfo>>&, mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::$_12&>(mlir::MLIRContext*, std::__1::vector<mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::OpPMInfo, std::__1::allocator<mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::OpPMInfo>>&, mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool)::$_12&) + 83
19 firtool                  0x000000010b279b73 mlir::detail::OpToOpPassAdaptor::runOnOperationAsyncImpl(bool) + 1187
20 firtool                  0x000000010b2788f7 mlir::detail::OpToOpPassAdaptor::runOnOperation(bool) + 71
21 firtool                  0x000000010b27854a mlir::detail::OpToOpPassAdaptor::run(mlir::Pass*, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int) + 602
22 firtool                  0x000000010b278d26 mlir::detail::OpToOpPassAdaptor::runPipeline(mlir::OpPassManager&, mlir::Operation*, mlir::AnalysisManager, bool, unsigned int, mlir::PassInstrumentor*, mlir::PassInstrumentation::PipelineParentInfo const*) + 390
23 firtool                  0x000000010b27b26c mlir::PassManager::runPasses(mlir::Operation*, mlir::AnalysisManager) + 108
24 firtool                  0x000000010b27b025 mlir::PassManager::run(mlir::Operation*) + 885
25 firtool                  0x000000010a18468f processBuffer(mlir::MLIRContext&, mlir::TimingScope&, llvm::SourceMgr&, llvm::Optional<std::__1::unique_ptr<llvm::ToolOutputFile, std::__1::default_delete<llvm::ToolOutputFile>>>&) + 6719
26 firtool                  0x000000010a182a36 processInputSplit(mlir::MLIRContext&, mlir::TimingScope&, std::__1::unique_ptr<llvm::MemoryBuffer, std::__1::default_delete<llvm::MemoryBuffer>>, llvm::Optional<std::__1::unique_ptr<llvm::ToolOutputFile, std::__1::default_delete<llvm::ToolOutputFile>>>&) + 246
27 firtool                  0x000000010a17f0fd processInput(mlir::MLIRContext&, mlir::TimingScope&, std::__1::unique_ptr<llvm::MemoryBuffer, std::__1::default_delete<llvm::MemoryBuffer>>, llvm::Optional<std::__1::unique_ptr<llvm::ToolOutputFile, std::__1::default_delete<llvm::ToolOutputFile>>>&) + 109
28 firtool                  0x000000010a178114 executeFirtool(mlir::MLIRContext&) + 1156
29 firtool                  0x000000010a177b84 main + 276
30 dyld                     0x0000000115e1b51e start + 462

I'm working on putting together a minimal input that duplicates the issue that I'd be able to share, but so far I haven't had luck duplicating the segfault. The design I'm testing on has a few modules that need to be deduplicated, but the majority of the design has a lot of multiply-instantiated modules, so we're extensively using the Chisel 3.5 Instance/Definition feature to cut down on the dedup work.

The issue appears to come from the part of the pass where we iterate over the instance graph with the llvm::post_order iterator, and then remove elements from that graph when we detect a duplicate module. Here is where the segfault comes from:

https://github.com/llvm/circt/blob/23ae1a7391c3d4d03eceade2189e224c4bb1ebaf/lib/Dialect/FIRRTL/Transforms/Dedup.cpp#L1172

And here is where the instanceGraph is modified within the loop iteration:

https://github.com/llvm/circt/blob/23ae1a7391c3d4d03eceade2189e224c4bb1ebaf/lib/Dialect/FIRRTL/Transforms/Dedup.cpp#L1192

Given the presence of this comment, this issue was certainly foreseen, but something about my design is still triggering this problem.

I was able to make the following change to resolve the segfault:

diff --git a/lib/Dialect/FIRRTL/Transforms/Dedup.cpp b/lib/Dialect/FIRRTL/Transforms/Dedup.cpp
index a65d1d25..2286386c 100644
--- a/lib/Dialect/FIRRTL/Transforms/Dedup.cpp
+++ b/lib/Dialect/FIRRTL/Transforms/Dedup.cpp
@@ -1169,7 +1169,10 @@ class DedupPass : public DedupBase<DedupPass> {
     // We must iterate the modules from the bottom up so that we can properly
     // deduplicate the modules. We have to store the visit order first so that
     // we can safely delete nodes as we go from the instance graph.
-    for (auto *node : llvm::post_order(&instanceGraph)) {
+    auto i = llvm::po_begin(&instanceGraph);
+    auto e = llvm::po_end(&instanceGraph);
+    while (i != e) {
+      auto *node = *i++;
       auto module = cast<FModuleLike>(*node->getModule());
       auto moduleName = module.moduleNameAttr();
       // If the module is marked with NoDedup, just skip it.

However, I don't entirely understand why this has any different behavior, since the post_order(...) function creates an iterator out of the po_begin and po_end functions: https://github.com/llvm/llvm-project/blob/b422dac240f1475999a2c1b5fc242a0ef2e08727/llvm/include/llvm/ADT/PostOrderIterator.h#L182-L191

Then again, I'm no C++ expert, so it's likely there's something else going on (perhaps with the for-each loop syntax) that I don't yet understand. If there are any other tests I can try to narrow down the issue/solution, please let me know!

-Tynan

llvm / circt

[FIRRTL] Segfault in Dedup Pass #3360