feat: Modify dead code elimination pass to remove unreachable basic blocks#2884
feat: Modify dead code elimination pass to remove unreachable basic blocks#2884
Conversation
Codecov Report✅ All modified and coverable lines are covered by tests. Additional details and impacted files@@ Coverage Diff @@
## main #2884 +/- ##
==========================================
+ Coverage 83.81% 83.83% +0.01%
==========================================
Files 269 269
Lines 53967 54018 +51
Branches 47920 47971 +51
==========================================
+ Hits 45235 45286 +51
Misses 6317 6317
Partials 2415 2415
Flags with carried forward coverage won't be shown. Click here to find out more. ☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
acl-cqc
left a comment
acl-cqc
left a comment
There was a problem hiding this comment.
Thanks @tatiana-s! The logic looks fine+good; a few ideas/suggestions for tidying slightly, but only thing I'm really bothered about is that I would like to strengthen the test - we looked at diagrams to see the action was correct, which is much more than we are doing in the test at the moment.
hugr-passes/src/dead_code.rs
Outdated
| q.push_back(src); | ||
| if h.get_optype(n).is_dataflow_block() || h.get_optype(n).is_exit_block() { | ||
| // Follow control flow forwards to find reachable basic blocks besides entry and exit. | ||
| for src in h.output_neighbours(n) { |
There was a problem hiding this comment.
nit: does q.extend(h.output_neighbours(n)) work?
hugr-passes/src/dead_code.rs
Outdated
| } | ||
| } else { | ||
| // Follow dataflow demand (including e.g edges from Call to FuncDefn) backwards. | ||
| for src in h.input_neighbours(n) { |
There was a problem hiding this comment.
similarly q.extend(h.input_neighbours(n))
hugr-passes/src/dead_code.rs
Outdated
| || match h.get_optype(ch) { | ||
| OpType::Case(_) => true, // Include all Cases in Conditionals | ||
| OpType::DataflowBlock(_) => h.get_optype(n).is_cfg() && i == 0, // Assumes entry block is always the first child of a CFG. | ||
| OpType::ExitBlock(_) => true, |
There was a problem hiding this comment.
consider using | in the pattern....even
OpType::Case // Include all Cases in Conditionals
| OpType::ExitBlock
| OpType::AliasDecl` // and all aliases (we do not....
| OpType::Output
hugr-passes/src/dead_code.rs
Outdated
| OpType::AliasDefn(_) => true, | ||
| OpType::Input(_) => true, // Also Dataflow input/output, these are necessary for legality | ||
| OpType::Output(_) => true, | ||
| // Do not include FuncDecl / FuncDefn / Const unless reachable by static edges (from Call/LoadConst/LoadFunction) |
There was a problem hiding this comment.
nit: that is a super-long line
hugr-passes/src/dead_code.rs
Outdated
| // Following ControlFlow edges backwards is harmless, we've already assumed all | ||
| // BBs are reachable above. | ||
| q.push_back(src); | ||
| if h.get_optype(n).is_dataflow_block() || h.get_optype(n).is_exit_block() { |
There was a problem hiding this comment.
Consider match? Or matches!(h.get_optype(n), OpType::DataflowBlock(_) | OpType::ExitBlock(_))
hugr-passes/src/dead_code.rs
Outdated
| // Run pass and check that unreachable block is removed | ||
| DeadCodeElimPass::default().run(&mut h).unwrap(); | ||
| h.validate().unwrap(); | ||
| let num_nodes_after = h.nodes().count(); |
There was a problem hiding this comment.
I think nodes do not get renumbered unless we serialize, so you should be able to get that block_unreachable is no longer a valid node?
You could also check the number of children of the CFG, as that only goes down by one (which is a bit more obvious), and you can verify that the cfg node is still a cfg.
Each of those would be a slightly stronger check that we have done (removed) the right thing. Good to check total number of nodes too tho i.e. that we have removed the entire subtree not just one node!
Extra brownie points for checking that the remaining children of the CFG each have a single output-neighbour being the next child (child ordering stays consistent so this does not require searching); also that the exitblock has only one predecessor now.
acl-cqc
left a comment
acl-cqc
left a comment
There was a problem hiding this comment.
Looks great, thanks @tatiana-s, sorry for delay in rereview!
| h.validate().unwrap(); | ||
| let num_nodes_before = h.nodes().count(); | ||
| let cfg_node = h.entrypoint(); | ||
| let num_cfg_children_before: usize = h |
There was a problem hiding this comment.
Consider making this a closure that takes h as a parameter (but captures cfg_node, which is Copy so easy), so you can call it twice (once before, once after)
## 🤖 New release * `hugr-model`: 0.25.6 -> 0.25.7 (✓ API compatible changes) * `hugr-core`: 0.25.6 -> 0.25.7 (✓ API compatible changes) * `hugr-llvm`: 0.25.6 -> 0.25.7 (✓ API compatible changes) * `hugr-passes`: 0.25.6 -> 0.25.7 (✓ API compatible changes) * `hugr-persistent`: 0.4.6 -> 0.4.7 (✓ API compatible changes) * `hugr`: 0.25.6 -> 0.25.7 (✓ API compatible changes) * `hugr-cli`: 0.25.6 -> 0.25.7 (✓ API compatible changes) <details><summary><i><b>Changelog</b></i></summary><p> ## `hugr-model` <blockquote> ## [0.25.6](hugr-model-v0.25.5...hugr-model-v0.25.6) - 2026-02-20 ### New Features - Remove size limitation for binary envelopes ([#2880](#2880)) </blockquote> ## `hugr-core` <blockquote> ## [0.25.7](hugr-core-v0.25.6...hugr-core-v0.25.7) - 2026-03-06 ### Documentation - added examples in docs srtring ([#2920](#2920)) </blockquote> ## `hugr-llvm` <blockquote> ## [0.25.6](hugr-llvm-v0.25.5...hugr-llvm-v0.25.6) - 2026-02-20 ### New Features - Add error context when lowering hugrs to LLVM ([#2869](#2869)) </blockquote> ## `hugr-passes` <blockquote> ## [0.25.7](hugr-passes-v0.25.6...hugr-passes-v0.25.7) - 2026-03-06 ### Documentation - added examples in docs srtring ([#2920](#2920)) ### New Features - Define pass application scopes ([#2772](#2772)) - Modify dead code elimination pass to remove unreachable basic blocks ([#2884](#2884)) - Add non-generic `with_scope` method for composable passes ([#2910](#2910)) - update passes to use PassScope where non-breaking ([#2836](#2836)) </blockquote> ## `hugr-persistent` <blockquote> ## [0.4.0](hugr-persistent-v0.3.4...hugr-persistent-v0.4.0) - 2025-12-22 ### New Features - [**breaking**] Remove `RootCheckable` ([#2704](#2704)) - [**breaking**] Bump MSRV to Rust 1.89 ([#2747](#2747)) - [**breaking**] Type-safe access for node metadata ([#2755](#2755)) ### Refactor - [**breaking**] Remove multiple deprecated definitions ([#2751](#2751)) </blockquote> ## `hugr` <blockquote> ## [0.25.7](hugr-v0.25.6...hugr-v0.25.7) - 2026-03-06 ### Documentation - added examples in docs srtring ([#2920](#2920)) ### New Features - Define pass application scopes ([#2772](#2772)) - Modify dead code elimination pass to remove unreachable basic blocks ([#2884](#2884)) - Add non-generic `with_scope` method for composable passes ([#2910](#2910)) - update passes to use PassScope where non-breaking ([#2836](#2836)) </blockquote> ## `hugr-cli` <blockquote> ## [0.25.6](hugr-cli-v0.25.5...hugr-cli-v0.25.6) - 2026-02-20 ### New Features - Add s expression format to envelope formats ([#2864](#2864)) </blockquote> </p></details> --- This PR was generated with [release-plz](https://github.com/release-plz/release-plz/).
2 participants
Closes #2597