palladium/optimizer/
dead_code.rs

1//! Dead code elimination pass
2//!
3//! This pass removes unreachable code and statements with no effect
4
5use crate::ast::*;
6use crate::errors::CompileError;
7use crate::optimizer::{helpers, OptimizationPass};
8
9pub struct DeadCodeEliminationPass {
10    changes_made: usize,
11}
12
13impl Default for DeadCodeEliminationPass {
14    fn default() -> Self {
15        Self::new()
16    }
17}
18
19impl DeadCodeEliminationPass {
20    pub fn new() -> Self {
21        Self { changes_made: 0 }
22    }
23
24    /// Check if control flow can continue after a statement
25    #[allow(clippy::only_used_in_recursion)]
26    fn can_continue_after(&self, stmt: &Stmt) -> bool {
27        match stmt {
28            Stmt::Return(_) | Stmt::Break { .. } | Stmt::Continue { .. } => false,
29            Stmt::If {
30                then_branch,
31                else_branch,
32                ..
33            } => {
34                // Control can continue if either branch can continue
35                let then_can_continue =
36                    then_branch.is_empty() || self.can_continue_after(then_branch.last().unwrap());
37
38                let else_can_continue = else_branch.as_ref().is_none_or(|branch| {
39                    branch.is_empty() || self.can_continue_after(branch.last().unwrap())
40                });
41
42                then_can_continue || else_can_continue
43            }
44            _ => true,
45        }
46    }
47}
48
49impl OptimizationPass for DeadCodeEliminationPass {
50    fn name(&self) -> &str {
51        "Dead Code Elimination"
52    }
53
54    fn optimize_program(&mut self, program: &mut Program) -> Result<bool, CompileError> {
55        self.changes_made = 0;
56
57        for item in &mut program.items {
58            if let Item::Function(func) = item {
59                self.optimize_function(func)?;
60            }
61        }
62
63        Ok(self.changes_made > 0)
64    }
65
66    fn optimize_function(&mut self, func: &mut Function) -> Result<bool, CompileError> {
67        self.eliminate_dead_code_in_vec(&mut func.body)
68    }
69
70    fn optimize_statement(&mut self, stmt: &mut Stmt) -> Result<bool, CompileError> {
71        match stmt {
72            Stmt::If {
73                condition,
74                then_branch,
75                else_branch,
76                ..
77            } => {
78                // Check for constant conditions
79                if let Expr::Bool(_val) = condition {
80                    // Note: Statement-level transformations would require returning
81                    // a replacement statement or modifying the parent's statement list.
82                    // This is beyond the scope of the current optimization framework,
83                    // which only modifies expressions in-place.
84                    // A production compiler would use an IR that supports these transforms.
85                    self.changes_made += 1;
86                }
87
88                self.eliminate_dead_code_in_vec(then_branch)?;
89
90                if let Some(else_branch) = else_branch {
91                    self.eliminate_dead_code_in_vec(else_branch)?;
92                }
93            }
94            Stmt::While {
95                condition, body, ..
96            } => {
97                // Check for constant false condition
98                if let Expr::Bool(false) = condition {
99                    // Note: Removing the entire while loop would require modifying
100                    // the parent's statement list, which our current framework doesn't support.
101                    // In a production compiler, this would be done on an IR.
102                    self.changes_made += 1;
103                }
104
105                self.eliminate_dead_code_in_vec(body)?;
106            }
107            Stmt::Expr(expr) => {
108                // Remove expressions with no side effects
109                if !helpers::expr_has_side_effects(expr) {
110                    // Note: Removing statements requires modifying the parent's statement list.
111                    // Our current framework doesn't support this level of transformation.
112                    self.changes_made += 1;
113                    return Ok(true);
114                }
115            }
116            _ => {}
117        }
118
119        Ok(false)
120    }
121
122    fn optimize_expression(&mut self, _expr: &mut Expr) -> Result<bool, CompileError> {
123        // Dead code elimination doesn't modify expressions
124        Ok(false)
125    }
126}
127
128impl DeadCodeEliminationPass {
129    /// Eliminate dead code in a vector of statements
130    fn eliminate_dead_code_in_vec(
131        &mut self,
132        statements: &mut Vec<Stmt>,
133    ) -> Result<bool, CompileError> {
134        let mut i = 0;
135        let mut found_terminator = false;
136
137        while i < statements.len() {
138            let stmt = &statements[i];
139
140            if found_terminator {
141                // Remove all statements after a terminator
142                statements.truncate(i);
143                self.changes_made += 1;
144                return Ok(true);
145            }
146
147            // Check if this statement is a terminator
148            if !self.can_continue_after(stmt) {
149                found_terminator = true;
150            }
151
152            // Optimize the statement itself
153            self.optimize_statement(&mut statements[i])?;
154
155            i += 1;
156        }
157
158        Ok(false)
159    }
160}
palladium/optimizer/dead_code.rs

palladium/optimizer/
dead_code.rs
