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, 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            Async(_) => false,
63            Binary(bin) => {
64                use BinaryOperation::*;
65                let halting_op = match bin.op {
66                    // These can halt for any of their operand types.
67                    Div | Mod | Rem | Shl | Shr => true,
68                    // These can only halt for integers.
69                    Add | Mul | Pow => {
70                        matches!(
71                            self.state.type_table.get(&expr.id()).expect("Types should be assigned."),
72                            Type::Integer(..)
73                        )
74                    }
75                    _ => false,
76                };
77                !halting_op && sef(&bin.left) && sef(&bin.right)
78            }
79            Call(..) => {
80                // Since calls may halt, be conservative and don't consider any call side effect free.
81                false
82            }
83            Cast(..) => {
84                // At least for now, be conservative and don't consider any cast side effect free.
85                // Of course for some combinations of types, casts will never halt.
86                false
87            }
88            Struct(struct_) => struct_.members.iter().all(|mem| mem.expression.as_ref().is_none_or(sef)),
89            Ternary(tern) => [&tern.condition, &tern.if_true, &tern.if_false].into_iter().all(sef),
90            Tuple(tuple) => tuple.elements.iter().all(sef),
91            Unary(un) => {
92                use UnaryOperation::*;
93                let halting_op = match un.op {
94                    // These can halt for any of their operand types.
95                    Abs | Inverse | SquareRoot => true,
96                    // Negate can only halt for integers.
97                    Negate => {
98                        matches!(
99                            self.state.type_table.get(&expr.id()).expect("Type should be assigned."),
100                            Type::Integer(..)
101                        )
102                    }
103                    _ => false,
104                };
105                !halting_op && sef(&un.receiver)
106            }
107            Err(_) => false,
108            Path(_) | Literal(_) | Locator(_) | Unit(_) => true,
109        }
110    }
111}
leo_passes/dead_code_elimination/visitor.rs

leo_passes/dead_code_elimination/
visitor.rs
