leo_passes/dead_code_elimination/
visitor.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
17use crate::CompilerState;
18
19use leo_ast::{BinaryOperation, Expression, Node as _, Type, TypeReconstructor, UnaryOperation};
20use leo_span::{Symbol, sym};
21
22use indexmap::IndexSet;
23
24pub struct DeadCodeEliminatingVisitor<'a> {
25    pub state: &'a mut CompilerState,
26
27    /// The set of used variables in the current function body.
28    pub used_variables: IndexSet<Symbol>,
29
30    /// The name of the program currently being processed.
31    pub program_name: Symbol,
32
33    /// How many statements were in the AST before DCE?
34    pub statements_before: u32,
35
36    /// How many statements were in the AST after DCE?
37    pub statements_after: u32,
38}
39
40impl DeadCodeEliminatingVisitor<'_> {
41    pub fn side_effect_free(&self, expr: &Expression) -> bool {
42        use Expression::*;
43
44        let sef = |expr| self.side_effect_free(expr);
45
46        match expr {
47            ArrayAccess(array) => sef(&array.array) && sef(&array.index),
48            MemberAccess(mem) => sef(&mem.inner),
49            Repeat(repeat) => sef(&repeat.expr) && sef(&repeat.count),
50            TupleAccess(tuple) => sef(&tuple.tuple),
51            Array(array) => array.elements.iter().all(sef),
52            AssociatedConstant(_) => true,
53            AssociatedFunction(func) => {
54                // CheatCode, Mapping, and Future operations obviously have side effects.
55                // Pedersen64 and Pedersen128 operations can fail for large inputs.
56                func.arguments.iter().all(sef)
57                    && !matches!(
58                        func.variant.name,
59                        sym::CheatCode | sym::Mapping | sym::Future | sym::Pedersen64 | sym::Pedersen128
60                    )
61            }
62            Binary(bin) => {
63                use BinaryOperation::*;
64                let halting_op = match bin.op {
65                    // These can halt for any of their operand types.
66                    Div | Mod | Rem | Shl | Shr => true,
67                    // These can only halt for integers.
68                    Add | Mul | Pow => {
69                        matches!(
70                            self.state.type_table.get(&expr.id()).expect("Types should be assigned."),
71                            Type::Integer(..)
72                        )
73                    }
74                    _ => false,
75                };
76                !halting_op && sef(&bin.left) && sef(&bin.right)
77            }
78            Call(..) => {
79                // Since calls may halt, be conservative and don't consider any call side effect free.
80                false
81            }
82            Cast(..) => {
83                // At least for now, be conservative and don't consider any cast side effect free.
84                // Of course for some combinations of types, casts will never halt.
85                false
86            }
87            Struct(struct_) => struct_.members.iter().all(|mem| mem.expression.as_ref().is_none_or(sef)),
88            Ternary(tern) => [&tern.condition, &tern.if_true, &tern.if_false].into_iter().all(sef),
89            Tuple(tuple) => tuple.elements.iter().all(sef),
90            Unary(un) => {
91                use UnaryOperation::*;
92                let halting_op = match un.op {
93                    // These can halt for any of their operand types.
94                    Abs | Inverse | SquareRoot => true,
95                    // Negate can only halt for integers.
96                    Negate => {
97                        matches!(
98                            self.state.type_table.get(&expr.id()).expect("Type should be assigned."),
99                            Type::Integer(..)
100                        )
101                    }
102                    _ => false,
103                };
104                !halting_op && sef(&un.receiver)
105            }
106            Err(_) => false,
107            Identifier(_) | Literal(_) | Locator(_) | Unit(_) => true,
108        }
109    }
110}
111
112impl TypeReconstructor for DeadCodeEliminatingVisitor<'_> {}
leo_passes/dead_code_elimination/visitor.rs

leo_passes/dead_code_elimination/
visitor.rs
