leo_passes/dead_code_elimination/mod.rs
1// Copyright (C) 2019-2025 Provable Inc.
2// This file is part of the Leo library.
3
4// The Leo library is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8
9// The Leo library is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12// GNU General Public License for more details.
13
14// You should have received a copy of the GNU General Public License
15// along with the Leo library. If not, see <https://www.gnu.org/licenses/>.
16
17//! The Dead Code Elimination pass traverses the AST and eliminates unused code,
18//! specifically assignment statements, within the boundary of `transition`s and `function`s.
19//! The pass is run after the Function Inlining pass.
20//!
21//! See https://en.wikipedia.org/wiki/Dead-code_elimination for more information.
22//!
23//! Consider the following flattened Leo code.
24//! ```leo
25//! function main(flag: u8, value: u8) -> u8 {
26//! $var$0 = flag == 0u8;
27//! $var$4$5 = value * value;
28//! $var$1 = $var$4$5;
29//! value$2 = $var$1;
30//! value$3 = $var$0 ? value$2 : value;
31//! value$6 = $var$1 * $var$1;
32//! return value$3;
33//! }
34//! ```
35//!
36//! The dead code elimination pass produces the following code.
37//! ```leo
38//! function main(flag: u8, value: u8) -> u8 {
39//! $var$0 = flag == 0u8;
40//! $var$4$5 = value * value;
41//! $var$1 = $var$4$5;
42//! value$2 = $var$1;
43//! value$3 = $var$0 ? value$2 : value;
44//! return value$3;
45//! }
46//! ```
47//! Note this pass relies on the following invariants:
48//! - No shadowing for all variables, struct names, function names, etc.
49//! - Unique variable names (provided by SSA)
50//! - Flattened code (provided by the flattening pass)
51
52use crate::Pass;
53
54use leo_ast::ProgramReconstructor as _;
55use leo_errors::Result;
56
57mod expression;
58
59mod program;
60
61mod statement;
62
63mod visitor;
64use visitor::*;
65
66pub struct DeadCodeEliminatingOutput {
67 pub statements_before: u32,
68 pub statements_after: u32,
69}
70
71pub struct DeadCodeEliminating;
72
73impl Pass for DeadCodeEliminating {
74 type Input = ();
75 type Output = DeadCodeEliminatingOutput;
76
77 const NAME: &str = "DeadCodeEliminating";
78
79 fn do_pass(_input: Self::Input, state: &mut crate::CompilerState) -> Result<Self::Output> {
80 let mut ast = std::mem::take(&mut state.ast);
81 let mut visitor = DeadCodeEliminatingVisitor {
82 state,
83 used_variables: Default::default(),
84 program_name: Default::default(),
85 statements_before: 0,
86 statements_after: 0,
87 };
88 ast.ast = visitor.reconstruct_program(ast.ast);
89 visitor.state.handler.last_err().map_err(|e| *e)?;
90 visitor.state.ast = ast;
91 Ok(DeadCodeEliminatingOutput {
92 statements_before: visitor.statements_before,
93 statements_after: visitor.statements_after,
94 })
95 }
96}