leo_passes/
library_pruning.rs

1// Copyright (C) 2019-2026 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//! Drops library functions the program can never reach.
18//!
19//! `std` is injected into every program as a `FromLibrary` stub, so otherwise every compile drags
20//! all ~6,000 of its functions through the backend before dead-code elimination discards the
21//! unused ones. This pass removes library functions not transitively reachable from any
22//! non-library function, using the call graph that type checking just built.
23//!
24//! This complements [`crate::DeadCodeEliminating`], which drops uncalled functions within a
25//! program but is a no-op for libraries; library stubs are pruned here instead.
26
27use crate::{CompilerState, Pass};
28
29use leo_ast::{Ast, Library, Location, Stub};
30use leo_errors::Result;
31
32use indexmap::IndexSet;
33
34/// Pass that prunes unreachable functions from `FromLibrary` stubs.
35pub struct LibraryPruning;
36
37impl Pass for LibraryPruning {
38    type Input = ();
39    type Output = ();
40
41    const NAME: &str = "LibraryPruning";
42
43    fn do_pass(_input: Self::Input, state: &mut CompilerState) -> Result<Self::Output> {
44        // This pass runs in the program backend, which a library build skips (frontend only, no
45        // bytecode), so it never sees an `Ast::Library`. The guard skips programs that import no
46        // library (e.g. `no_std`); otherwise every `FromLibrary` stub below is pruned, std included.
47        let has_library_stub = matches!(&state.ast, Ast::Program(p)
48            if p.stubs.values().any(|s| matches!(s, Stub::FromLibrary { .. })));
49        if !has_library_stub {
50            return Ok(());
51        }
52
53        // Reachability via a single multi-source traversal from every non-library function. Every
54        // non-library function is a root, not just entry points, so a library function called from
55        // any imported program survives even when the caller is itself unreachable.
56        let mut reachable: IndexSet<Location> = IndexSet::new();
57        let mut queue: Vec<Location> = Vec::new();
58        for node in state.call_graph.nodes() {
59            if !state.symbol_table.is_library(node.program) {
60                queue.extend(state.call_graph.neighbors(node).cloned());
61            }
62        }
63        while let Some(node) = queue.pop() {
64            if reachable.insert(node.clone()) {
65                queue.extend(state.call_graph.neighbors(&node).cloned());
66            }
67        }
68
69        let Ast::Program(program) = &mut state.ast else { unreachable!("checked above") };
70        for stub in program.stubs.values_mut() {
71            if let Stub::FromLibrary { library, .. } = stub {
72                prune_library(library, &reachable);
73            }
74        }
75
76        Ok(())
77    }
78}
79
80/// Removes functions not in `reachable` from `library` and its submodules. Structs, consts, and
81/// interfaces are kept for now.
82fn prune_library(library: &mut Library, reachable: &IndexSet<Location>) {
83    let declares_const = !library.consts.is_empty() || library.modules.values().any(|module| !module.consts.is_empty());
84    if declares_const {
85        return;
86    }
87
88    let name = library.name;
89    library.functions.retain(|(symbol, _)| reachable.contains(&Location::new(name, vec![*symbol])));
90
91    for (path, module) in &mut library.modules {
92        let program = module.unit_name;
93        module.functions.retain(|(symbol, _)| {
94            let mut full_path = Vec::with_capacity(path.len() + 1);
95            full_path.extend_from_slice(path);
96            full_path.push(*symbol);
97            reachable.contains(&Location::new(program, full_path))
98        });
99    }
100}
leo_passes/library_pruning.rs

leo_passes/
library_pruning.rs
