leo-passes 2.5.0

Compiler passes for the Leo programming language
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

// Copyright (C) 2019-2025 Provable Inc.
// This file is part of the Leo library.

// The Leo library is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// The Leo library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with the Leo library. If not, see <https://www.gnu.org/licenses/>.

use leo_ast::{AccessExpression, BinaryOperation, Expression, Node as _, Type, UnaryOperation};
use leo_span::{Symbol, sym};

use indexmap::IndexSet;

use crate::TypeTable;

#[derive(Debug)]
pub struct DeadCodeEliminator<'a> {
    /// The set of used variables in the current function body.
    pub(crate) used_variables: IndexSet<Symbol>,

    /// The name of the program currently being processed.
    pub(crate) program_name: Symbol,

    /// The `TypeTable` of the code being processed.
    pub(crate) type_table: &'a TypeTable,

    /// How many statements were in the AST before DCE?
    pub(crate) statements_before: u32,

    /// How many statements were in the AST after DCE?
    pub(crate) statements_after: u32,
}

impl<'a> DeadCodeEliminator<'a> {
    /// Initializes a new `DeadCodeEliminator`.
    pub(crate) fn new(type_table: &'a TypeTable) -> Self {
        Self {
            used_variables: Default::default(),
            program_name: Symbol::intern(""),
            type_table,
            statements_before: 0,
            statements_after: 0,
        }
    }

    pub(crate) fn side_effect_free(&self, expr: &Expression) -> bool {
        use Expression::*;

        let sef = |expr| self.side_effect_free(expr);

        match expr {
            Access(AccessExpression::Array(array)) => sef(&array.array) && sef(&array.index),
            Access(AccessExpression::Member(mem)) => sef(&mem.inner),
            Access(AccessExpression::Tuple(tuple)) => sef(&tuple.tuple),
            Array(array) => array.elements.iter().all(sef),
            AssociatedConstant(_) => true,
            AssociatedFunction(func) => {
                // CheatCode, Mapping, and Future operations obviously have side effects.
                // Pedersen64 and Pedersen128 operations can fail for large inputs.
                func.arguments.iter().all(sef)
                    && !matches!(
                        func.variant.name,
                        sym::CheatCode | sym::Mapping | sym::Future | sym::Pedersen64 | sym::Pedersen128
                    )
            }
            Binary(bin) => {
                use BinaryOperation::*;
                let halting_op = match bin.op {
                    // These can halt for any of their operand types.
                    Div | Mod | Rem | Shl | Shr => true,
                    // These can only halt for integers.
                    Add | Mul | Pow => {
                        matches!(self.type_table.get(&expr.id()).expect("Types should be assigned."), Type::Integer(..))
                    }
                    _ => false,
                };
                !halting_op && sef(&bin.left) && sef(&bin.right)
            }
            Call(..) => {
                // Since calls may halt, be conservative and don't consider any call side effect free.
                false
            }
            Cast(..) => {
                // At least for now, be conservative and don't consider any cast side effect free.
                // Of course for some combinations of types, casts will never halt.
                false
            }
            Struct(struct_) => struct_.members.iter().all(|mem| mem.expression.as_ref().is_none_or(sef)),
            Ternary(tern) => [&*tern.condition, &*tern.if_true, &*tern.if_false].into_iter().all(sef),
            Tuple(tuple) => tuple.elements.iter().all(sef),
            Unary(un) => {
                use UnaryOperation::*;
                let halting_op = match un.op {
                    // These can halt for any of their operand types.
                    Abs | Inverse | SquareRoot => true,
                    // Negate can only halt for integers.
                    Negate => {
                        matches!(self.type_table.get(&expr.id()).expect("Type should be assigned."), Type::Integer(..))
                    }
                    _ => false,
                };
                !halting_op && sef(&un.receiver)
            }
            Err(_) => false,
            Identifier(_) | Literal(_) | Locator(_) | Unit(_) => true,
        }
    }
}