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}