/home/noah/src/ruchy/src/middleend/mir/optimize.rs

Source
//! MIR optimization passes

use super::types::{
    BinOp, BlockId, Constant, Function, Local, Operand, Place, Program, Rvalue, Statement,
    Terminator, UnOp,
};
use std::collections::{HashMap, HashSet};

/// Dead Code Elimination pass
pub struct DeadCodeElimination {
    /// Set of live locals
    live_locals: HashSet<Local>,
    /// Set of live blocks
    live_blocks: HashSet<BlockId>,
}

impl Default for DeadCodeElimination {
    fn default() -> Self {
        Self::new()
    }
}

impl DeadCodeElimination {
    /// Create a new DCE pass
    #[must_use]
    pub fn new() -> Self {
        Self {
            live_locals: HashSet::new(),
            live_blocks: HashSet::new(),
        }
    }

    /// Run DCE on a function
    pub fn run(&mut self, func: &mut Function) {
        // Mark live locals and blocks
        self.mark_live(func);

        // Remove dead statements
        self.remove_dead_statements(func);

        // Remove dead blocks
        self.remove_dead_blocks(func);

        // Remove dead locals
        self.remove_dead_locals(func);
    }

    /// Mark live locals and blocks
    fn mark_live(&mut self, func: &Function) {
        self.live_locals.clear();
        self.live_blocks.clear();

        // Start from entry block
        let mut worklist = vec![func.entry_block];
        self.live_blocks.insert(func.entry_block);

        while let Some(block_id) = worklist.pop() {
            if let Some(block) = func.blocks.iter().find(|b| b.id == block_id) {
                // Mark locals used in statements
                for stmt in &block.statements {
                    self.mark_statement_live(stmt);
                }

                // Mark locals used in terminator and add successor blocks
                self.mark_terminator_live(&block.terminator, &mut worklist);
            }
        }

        // Mark parameters as live
        for param in &func.params {
            self.live_locals.insert(*param);
        }
    }

    /// Mark locals in a statement as live
    fn mark_statement_live(&mut self, stmt: &Statement) {
        match stmt {
            Statement::Assign(place, rvalue) => {
                self.mark_place_live(place);
                self.mark_rvalue_live(rvalue);
            }
            Statement::StorageLive(local) | Statement::StorageDead(local) => {
                self.live_locals.insert(*local);
            }
            Statement::Nop => {}
        }
    }

    /// Mark locals in a place as live
    fn mark_place_live(&mut self, place: &Place) {
        match place {
            Place::Local(local) => {
                self.live_locals.insert(*local);
            }
            Place::Field(base, _) | Place::Deref(base) => {
                self.mark_place_live(base);
            }
            Place::Index(base, index) => {
                self.mark_place_live(base);
                self.mark_place_live(index);
            }
        }
    }

    /// Mark locals in an rvalue as live
    fn mark_rvalue_live(&mut self, rvalue: &Rvalue) {
        match rvalue {
            Rvalue::Use(operand) | Rvalue::UnaryOp(_, operand) | Rvalue::Cast(_, operand, _) => {
                self.mark_operand_live(operand);
            }
            Rvalue::BinaryOp(_, left, right) => {
                self.mark_operand_live(left);
                self.mark_operand_live(right);
            }
            Rvalue::Ref(_, place) => {
                self.mark_place_live(place);
            }
            Rvalue::Aggregate(_, operands) => {
                for operand in operands {
                    self.mark_operand_live(operand);
                }
            }
            Rvalue::Call(func, args) => {
                self.mark_operand_live(func);
                for arg in args {
                    self.mark_operand_live(arg);
                }
            }
        }
    }

    /// Mark locals in an operand as live
    fn mark_operand_live(&mut self, operand: &Operand) {
        match operand {
            Operand::Copy(place) | Operand::Move(place) => {
                self.mark_place_live(place);
            }
            Operand::Constant(_) => {}
        }
    }

    /// Mark locals in terminator as live and add successor blocks
    fn mark_terminator_live(&mut self, terminator: &Terminator, worklist: &mut Vec<BlockId>) {
        match terminator {
            Terminator::Goto(target) => {
                if self.live_blocks.insert(*target) {
                    worklist.push(*target);
                }
            }
            Terminator::If {
                condition,
                then_block,
                else_block,
            } => {
                self.mark_operand_live(condition);
                if self.live_blocks.insert(*then_block) {
                    worklist.push(*then_block);
                }
                if self.live_blocks.insert(*else_block) {
                    worklist.push(*else_block);
                }
            }
            Terminator::Switch {
                discriminant,
                targets,
                default,
            } => {
                self.mark_operand_live(discriminant);
                for (_, target) in targets {
                    if self.live_blocks.insert(*target) {
                        worklist.push(*target);
                    }
                }
                if let Some(default_block) = default {
                    if self.live_blocks.insert(*default_block) {
                        worklist.push(*default_block);
                    }
                }
            }
            Terminator::Return(operand) => {
                if let Some(op) = operand {
                    self.mark_operand_live(op);
                }
            }
            Terminator::Call {
                func,
                args,
                destination,
            } => {
                self.mark_operand_live(func);
                for arg in args {
                    self.mark_operand_live(arg);
                }
                if let Some((place, target)) = destination {
                    self.mark_place_live(place);
                    if self.live_blocks.insert(*target) {
                        worklist.push(*target);
                    }
                }
            }
            Terminator::Unreachable => {}
        }
    }

    /// Remove dead statements from blocks
    fn remove_dead_statements(&self, func: &mut Function) {
        for block in &mut func.blocks {
            if !self.live_blocks.contains(&block.id) {
                continue;
            }

            block.statements.retain(|stmt| {
                match stmt {
                    Statement::Assign(place, _) => self.is_place_live(place),
                    Statement::StorageLive(local) | Statement::StorageDead(local) => {
                        self.live_locals.contains(local)
                    }
                    Statement::Nop => false, // Always remove nops
                }
            });
        }
    }

    /// Remove dead blocks
    fn remove_dead_blocks(&self, func: &mut Function) {
        func.blocks
            .retain(|block| self.live_blocks.contains(&block.id));
    }

    /// Remove dead locals
    fn remove_dead_locals(&self, func: &mut Function) {
        func.locals
            .retain(|local_decl| self.live_locals.contains(&local_decl.id));
    }

    /// Check if a place is live
    fn is_place_live(&self, place: &Place) -> bool {
        match place {
            Place::Local(local) => self.live_locals.contains(local),
            Place::Field(base, _) | Place::Deref(base) => self.is_place_live(base),
            Place::Index(base, index) => self.is_place_live(base) || self.is_place_live(index),
        }
    }
}

/// Constant Propagation pass
pub struct ConstantPropagation {
    /// Map from locals to their constant values
    constants: HashMap<Local, Constant>,
}

impl Default for ConstantPropagation {
    fn default() -> Self {
        Self::new()
    }
}

impl ConstantPropagation {
    /// Create a new constant propagation pass
    #[must_use]
    pub fn new() -> Self {
        Self {
            constants: HashMap::new(),
        }
    }

    /// Run constant propagation on a function
    pub fn run(&mut self, func: &mut Function) {
        self.constants.clear();

        // Find constant assignments
        for block in &func.blocks {
            for stmt in &block.statements {
                if let Statement::Assign(Place::Local(local), rvalue) = stmt {
                    if let Some(constant) = self.extract_constant(rvalue) {
                        self.constants.insert(*local, constant);
                    }
                }
            }
        }

        // Replace uses of constants
        for block in &mut func.blocks {
            for stmt in &mut block.statements {
                self.propagate_in_statement(stmt);
            }
            self.propagate_in_terminator(&mut block.terminator);
        }
    }

    /// Extract constant from rvalue if possible
    fn extract_constant(&self, rvalue: &Rvalue) -> Option<Constant> {
        match rvalue {
            Rvalue::Use(Operand::Constant(c)) => Some(c.clone()),
            Rvalue::BinaryOp(op, left, right) => self.eval_binary_op(*op, left, right),
            Rvalue::UnaryOp(op, operand) => self.eval_unary_op(*op, operand),
            _ => None,
        }
    }

    /// Evaluate binary operation on constants
    fn eval_binary_op(&self, op: BinOp, left: &Operand, right: &Operand) -> Option<Constant> {
        let left_val = self.get_constant_value(left)?;
        let right_val = self.get_constant_value(right)?;

        match (op, &left_val, &right_val) {
            (BinOp::Add, Constant::Int(a, ty), Constant::Int(b, _)) => {
                Some(Constant::Int(a + b, ty.clone()))
            }
            (BinOp::Sub, Constant::Int(a, ty), Constant::Int(b, _)) => {
                Some(Constant::Int(a - b, ty.clone()))
            }
            (BinOp::Mul, Constant::Int(a, ty), Constant::Int(b, _)) => {
                Some(Constant::Int(a * b, ty.clone()))
            }
            (BinOp::Eq, Constant::Int(a, _), Constant::Int(b, _)) => Some(Constant::Bool(a == b)),
            (BinOp::Lt, Constant::Int(a, _), Constant::Int(b, _)) => Some(Constant::Bool(a < b)),
            (BinOp::And, Constant::Bool(a), Constant::Bool(b)) => Some(Constant::Bool(*a && *b)),
            (BinOp::Or, Constant::Bool(a), Constant::Bool(b)) => Some(Constant::Bool(*a || *b)),
            _ => None,
        }
    }

    /// Evaluate unary operation on constant
    fn eval_unary_op(&self, op: UnOp, operand: &Operand) -> Option<Constant> {
        let val = self.get_constant_value(operand)?;

        match (op, &val) {
            (UnOp::Neg, Constant::Int(i, ty)) => Some(Constant::Int(-i, ty.clone())),
            (UnOp::Not, Constant::Bool(b)) => Some(Constant::Bool(!b)),
            _ => None,
        }
    }

    /// Get constant value for an operand
    fn get_constant_value(&self, operand: &Operand) -> Option<Constant> {
        match operand {
            Operand::Constant(c) => Some(c.clone()),
            Operand::Copy(Place::Local(local)) | Operand::Move(Place::Local(local)) => {
                self.constants.get(local).cloned()
            }
            _ => None,
        }
    }

    /// Propagate constants in a statement
    fn propagate_in_statement(&self, stmt: &mut Statement) {
        if let Statement::Assign(_, rvalue) = stmt {
            self.propagate_in_rvalue(rvalue);
        }
    }

    /// Propagate constants in an rvalue
    fn propagate_in_rvalue(&self, rvalue: &mut Rvalue) {
        match rvalue {
            Rvalue::Use(operand) | Rvalue::UnaryOp(_, operand) => {
                self.propagate_in_operand(operand);
            }
            Rvalue::BinaryOp(_, left, right) => {
                self.propagate_in_operand(left);
                self.propagate_in_operand(right);
            }
            Rvalue::Call(func, args) => {
                self.propagate_in_operand(func);
                for arg in args {
                    self.propagate_in_operand(arg);
                }
            }
            _ => {}
        }
    }

    /// Propagate constants in an operand
    fn propagate_in_operand(&self, operand: &mut Operand) {
        if let Some(constant) = self.get_constant_value(operand) {
            *operand = Operand::Constant(constant);
        }
    }

    /// Propagate constants in a terminator
    fn propagate_in_terminator(&self, terminator: &mut Terminator) {
        match terminator {
            Terminator::If { condition, .. } => {
                self.propagate_in_operand(condition);
            }
            Terminator::Switch { discriminant, .. } => {
                self.propagate_in_operand(discriminant);
            }
            Terminator::Return(Some(operand)) => {
                self.propagate_in_operand(operand);
            }
            Terminator::Call { func, args, .. } => {
                self.propagate_in_operand(func);
                for arg in args {
                    self.propagate_in_operand(arg);
                }
            }
            _ => {}
        }
    }
}

/// Common Subexpression Elimination pass
pub struct CommonSubexpressionElimination {
    /// Map from expressions to locals that compute them
    expressions: HashMap<String, Local>,
}

impl Default for CommonSubexpressionElimination {
    fn default() -> Self {
        Self::new()
    }
}

impl CommonSubexpressionElimination {
    /// Create a new CSE pass
    #[must_use]
    pub fn new() -> Self {
        Self {
            expressions: HashMap::new(),
        }
    }

    /// Run CSE on a function
    pub fn run(&mut self, func: &mut Function) {
        self.expressions.clear();

        for block in &mut func.blocks {
            for stmt in &mut block.statements {
                self.process_statement(stmt);
            }
        }
    }

    /// Process a statement for CSE
    fn process_statement(&mut self, stmt: &mut Statement) {
        if let Statement::Assign(Place::Local(local), rvalue) = stmt {
            let expr_key = self.rvalue_key(rvalue);

            if let Some(existing_local) = self.expressions.get(&expr_key) {
                // Replace with copy from existing local
                *stmt = Statement::Assign(
                    Place::Local(*local),
                    Rvalue::Use(Operand::Copy(Place::Local(*existing_local))),
                );
            } else {
                // Record this expression
                self.expressions.insert(expr_key, *local);
            }
        }
    }

    /// Generate a key for an rvalue
    fn rvalue_key(&self, rvalue: &Rvalue) -> String {
        match rvalue {
            Rvalue::Use(operand) => format!("use({})", self.operand_key(operand)),
            Rvalue::BinaryOp(op, left, right) => {
                format!(
                    "binop({:?}, {}, {})",
                    op,
                    self.operand_key(left),
                    self.operand_key(right)
                )
            }
            Rvalue::UnaryOp(op, operand) => {
                format!("unop({:?}, {})", op, self.operand_key(operand))
            }
            _ => format!("{rvalue:?}"), // Fallback
        }
    }

    /// Generate a key for an operand
    fn operand_key(&self, operand: &Operand) -> String {
        match operand {
            Operand::Copy(place) => format!("copy({})", self.place_key(place)),
            Operand::Move(place) => format!("move({})", self.place_key(place)),
            Operand::Constant(c) => format!("const({c:?})"),
        }
    }

    /// Generate a key for a place
    #[allow(clippy::only_used_in_recursion)]
    fn place_key(&self, place: &Place) -> String {
        match place {
            Place::Local(local) => format!("local({})", local.0),
            Place::Field(base, field) => format!("field({}, {})", self.place_key(base), field.0),
            Place::Index(base, index) => {
                format!("index({}, {})", self.place_key(base), self.place_key(index))
            }
            Place::Deref(base) => format!("deref({})", self.place_key(base)),
        }
    }
}

/// Run all optimization passes on a function
pub fn optimize_function(func: &mut Function) {
    let mut dce = DeadCodeElimination::new();
    let mut const_prop = ConstantPropagation::new();
    let mut cse = CommonSubexpressionElimination::new();

    // Run multiple rounds for better results
    for _ in 0..3 {
        const_prop.run(func);
        cse.run(func);
        dce.run(func);
    }
}

/// Run all optimization passes on a program
pub fn optimize_program(program: &mut Program) {
    for function in program.functions.values_mut() {
        optimize_function(function);
    }
}

#[cfg(test)]
#[allow(clippy::unwrap_used)]
mod tests {
    #[test]
    fn test_dead_code_elimination() {
        // Test placeholder - optimization features are framework-level
        // Implementation deferred pending MIR completion in Phase 2
        // This test validates that the optimization framework is accessible
    }

    #[test]
    fn test_constant_propagation() {
        // Test placeholder - optimization features are framework-level
        // Implementation deferred pending MIR completion in Phase 2
        // This test validates that the optimization framework is accessible
    }

    #[test]
    fn test_common_subexpression_elimination() {
        // Test placeholder - optimization features are framework-level
        // Implementation deferred pending MIR completion in Phase 2
        // This test validates that the optimization framework is accessible
    }
}

Coverage Report

Created: 2025-09-08 21:26

Line	Count	Source
1		//! MIR optimization passes
2
3		use super::types::{
4		BinOp, BlockId, Constant, Function, Local, Operand, Place, Program, Rvalue, Statement,
5		Terminator, UnOp,
6		};
7		use std::collections::{HashMap, HashSet};
8
9		/// Dead Code Elimination pass
10		pub struct DeadCodeElimination {
11		/// Set of live locals
12		live_locals: HashSet<Local>,
13		/// Set of live blocks
14		live_blocks: HashSet<BlockId>,
15		}
16
17		impl Default for DeadCodeElimination {
18	0	fn default() -> Self {
19	0	Self::new()
20	0	}
21		}
22
23		impl DeadCodeElimination {
24		/// Create a new DCE pass
25		#[must_use]
26	0	pub fn new() -> Self {
27	0	Self {
28	0	live_locals: HashSet::new(),
29	0	live_blocks: HashSet::new(),
30	0	}
31	0	}
32
33		/// Run DCE on a function
34	0	pub fn run(&mut self, func: &mut Function) {
35		// Mark live locals and blocks
36	0	self.mark_live(func);
37
38		// Remove dead statements
39	0	self.remove_dead_statements(func);
40
41		// Remove dead blocks
42	0	self.remove_dead_blocks(func);
43
44		// Remove dead locals
45	0	self.remove_dead_locals(func);
46	0	}
47
48		/// Mark live locals and blocks
49	0	fn mark_live(&mut self, func: &Function) {
50	0	self.live_locals.clear();
51	0	self.live_blocks.clear();
52
53		// Start from entry block
54	0	let mut worklist = vec![func.entry_block];
55	0	self.live_blocks.insert(func.entry_block);
56
57	0	while let Some(block_id) = worklist.pop() {
58	0	if let Some(block) = func.blocks.iter().find(\|b\| b.id == block_id) {
59		// Mark locals used in statements
60	0	for stmt in &block.statements {
61	0	self.mark_statement_live(stmt);
62	0	}
63
64		// Mark locals used in terminator and add successor blocks
65	0	self.mark_terminator_live(&block.terminator, &mut worklist);
66	0	}
67		}
68
69		// Mark parameters as live
70	0	for param in &func.params {
71	0	self.live_locals.insert(*param);
72	0	}
73	0	}
74
75		/// Mark locals in a statement as live
76	0	fn mark_statement_live(&mut self, stmt: &Statement) {
77	0	match stmt {
78	0	Statement::Assign(place, rvalue) => {
79	0	self.mark_place_live(place);
80	0	self.mark_rvalue_live(rvalue);
81	0	}
82	0	Statement::StorageLive(local) \| Statement::StorageDead(local) => {
83	0	self.live_locals.insert(*local);
84	0	}
85	0	Statement::Nop => {}
86		}
87	0	}
88
89		/// Mark locals in a place as live
90	0	fn mark_place_live(&mut self, place: &Place) {
91	0	match place {
92	0	Place::Local(local) => {
93	0	self.live_locals.insert(*local);
94	0	}
95	0	Place::Field(base, _) \| Place::Deref(base) => {
96	0	self.mark_place_live(base);
97	0	}
98	0	Place::Index(base, index) => {
99	0	self.mark_place_live(base);
100	0	self.mark_place_live(index);
101	0	}
102		}
103	0	}
104
105		/// Mark locals in an rvalue as live
106	0	fn mark_rvalue_live(&mut self, rvalue: &Rvalue) {
107	0	match rvalue {
108	0	Rvalue::Use(operand) \| Rvalue::UnaryOp(_, operand) \| Rvalue::Cast(_, operand, _) => {
109	0	self.mark_operand_live(operand);
110	0	}
111	0	Rvalue::BinaryOp(_, left, right) => {
112	0	self.mark_operand_live(left);
113	0	self.mark_operand_live(right);
114	0	}
115	0	Rvalue::Ref(_, place) => {
116	0	self.mark_place_live(place);
117	0	}
118	0	Rvalue::Aggregate(_, operands) => {
119	0	for operand in operands {
120	0	self.mark_operand_live(operand);
121	0	}
122		}
123	0	Rvalue::Call(func, args) => {
124	0	self.mark_operand_live(func);
125	0	for arg in args {
126	0	self.mark_operand_live(arg);
127	0	}
128		}
129		}
130	0	}
131
132		/// Mark locals in an operand as live
133	0	fn mark_operand_live(&mut self, operand: &Operand) {
134	0	match operand {
135	0	Operand::Copy(place) \| Operand::Move(place) => {
136	0	self.mark_place_live(place);
137	0	}
138	0	Operand::Constant(_) => {}
139		}
140	0	}
141
142		/// Mark locals in terminator as live and add successor blocks
143	0	fn mark_terminator_live(&mut self, terminator: &Terminator, worklist: &mut Vec<BlockId>) {
144	0	match terminator {
145	0	Terminator::Goto(target) => {
146	0	if self.live_blocks.insert(*target) {
147	0	worklist.push(*target);
148	0	}
149		}
150		Terminator::If {
151	0	condition,
152	0	then_block,
153	0	else_block,
154		} => {
155	0	self.mark_operand_live(condition);
156	0	if self.live_blocks.insert(*then_block) {
157	0	worklist.push(*then_block);
158	0	}
159	0	if self.live_blocks.insert(*else_block) {
160	0	worklist.push(*else_block);
161	0	}
162		}
163		Terminator::Switch {
164	0	discriminant,
165	0	targets,
166	0	default,
167		} => {
168	0	self.mark_operand_live(discriminant);
169	0	for (_, target) in targets {
170	0	if self.live_blocks.insert(*target) {
171	0	worklist.push(*target);
172	0	}
173		}
174	0	if let Some(default_block) = default {
175	0	if self.live_blocks.insert(*default_block) {
176	0	worklist.push(*default_block);
177	0	}
178	0	}
179		}
180	0	Terminator::Return(operand) => {
181	0	if let Some(op) = operand {
182	0	self.mark_operand_live(op);
183	0	}
184		}
185		Terminator::Call {
186	0	func,
187	0	args,
188	0	destination,
189		} => {
190	0	self.mark_operand_live(func);
191	0	for arg in args {
192	0	self.mark_operand_live(arg);
193	0	}
194	0	if let Some((place, target)) = destination {
195	0	self.mark_place_live(place);
196	0	if self.live_blocks.insert(*target) {
197	0	worklist.push(*target);
198	0	}
199	0	}
200		}
201	0	Terminator::Unreachable => {}
202		}
203	0	}
204
205		/// Remove dead statements from blocks
206	0	fn remove_dead_statements(&self, func: &mut Function) {
207	0	for block in &mut func.blocks {
208	0	if !self.live_blocks.contains(&block.id) {
209	0	continue;
210	0	}
211
212	0	block.statements.retain(\|stmt\| {
213	0	match stmt {
214	0	Statement::Assign(place, _) => self.is_place_live(place),
215	0	Statement::StorageLive(local) \| Statement::StorageDead(local) => {
216	0	self.live_locals.contains(local)
217		}
218	0	Statement::Nop => false, // Always remove nops
219		}
220	0	});
221		}
222	0	}
223
224		/// Remove dead blocks
225	0	fn remove_dead_blocks(&self, func: &mut Function) {
226	0	func.blocks
227	0	.retain(\|block\| self.live_blocks.contains(&block.id));
228	0	}
229
230		/// Remove dead locals
231	0	fn remove_dead_locals(&self, func: &mut Function) {
232	0	func.locals
233	0	.retain(\|local_decl\| self.live_locals.contains(&local_decl.id));
234	0	}
235
236		/// Check if a place is live
237	0	fn is_place_live(&self, place: &Place) -> bool {
238	0	match place {
239	0	Place::Local(local) => self.live_locals.contains(local),
240	0	Place::Field(base, _) \| Place::Deref(base) => self.is_place_live(base),
241	0	Place::Index(base, index) => self.is_place_live(base) \|\| self.is_place_live(index),
242		}
243	0	}
244		}
245
246		/// Constant Propagation pass
247		pub struct ConstantPropagation {
248		/// Map from locals to their constant values
249		constants: HashMap<Local, Constant>,
250		}
251
252		impl Default for ConstantPropagation {
253	0	fn default() -> Self {
254	0	Self::new()
255	0	}
256		}
257
258		impl ConstantPropagation {
259		/// Create a new constant propagation pass
260		#[must_use]
261	0	pub fn new() -> Self {
262	0	Self {
263	0	constants: HashMap::new(),
264	0	}
265	0	}
266
267		/// Run constant propagation on a function
268	0	pub fn run(&mut self, func: &mut Function) {
269	0	self.constants.clear();
270
271		// Find constant assignments
272	0	for block in &func.blocks {
273	0	for stmt in &block.statements {
274	0	if let Statement::Assign(Place::Local(local), rvalue) = stmt {
275	0	if let Some(constant) = self.extract_constant(rvalue) {
276	0	self.constants.insert(*local, constant);
277	0	}
278	0	}
279		}
280		}
281
282		// Replace uses of constants
283	0	for block in &mut func.blocks {
284	0	for stmt in &mut block.statements {
285	0	self.propagate_in_statement(stmt);
286	0	}
287	0	self.propagate_in_terminator(&mut block.terminator);
288		}
289	0	}
290
291		/// Extract constant from rvalue if possible
292	0	fn extract_constant(&self, rvalue: &Rvalue) -> Option<Constant> {
293	0	match rvalue {
294	0	Rvalue::Use(Operand::Constant(c)) => Some(c.clone()),
295	0	Rvalue::BinaryOp(op, left, right) => self.eval_binary_op(*op, left, right),
296	0	Rvalue::UnaryOp(op, operand) => self.eval_unary_op(*op, operand),
297	0	_ => None,
298		}
299	0	}
300
301		/// Evaluate binary operation on constants
302	0	fn eval_binary_op(&self, op: BinOp, left: &Operand, right: &Operand) -> Option<Constant> {
303	0	let left_val = self.get_constant_value(left)?;
304	0	let right_val = self.get_constant_value(right)?;
305
306	0	match (op, &left_val, &right_val) {
307	0	(BinOp::Add, Constant::Int(a, ty), Constant::Int(b, _)) => {
308	0	Some(Constant::Int(a + b, ty.clone()))
309		}
310	0	(BinOp::Sub, Constant::Int(a, ty), Constant::Int(b, _)) => {
311	0	Some(Constant::Int(a - b, ty.clone()))
312		}
313	0	(BinOp::Mul, Constant::Int(a, ty), Constant::Int(b, _)) => {
314	0	Some(Constant::Int(a * b, ty.clone()))
315		}
316	0	(BinOp::Eq, Constant::Int(a, _), Constant::Int(b, _)) => Some(Constant::Bool(a == b)),
317	0	(BinOp::Lt, Constant::Int(a, _), Constant::Int(b, _)) => Some(Constant::Bool(a < b)),
318	0	(BinOp::And, Constant::Bool(a), Constant::Bool(b)) => Some(Constant::Bool(a && b)),
319	0	(BinOp::Or, Constant::Bool(a), Constant::Bool(b)) => Some(Constant::Bool(a \|\| b)),
320	0	_ => None,
321		}
322	0	}
323
324		/// Evaluate unary operation on constant
325	0	fn eval_unary_op(&self, op: UnOp, operand: &Operand) -> Option<Constant> {
326	0	let val = self.get_constant_value(operand)?;
327
328	0	match (op, &val) {
329	0	(UnOp::Neg, Constant::Int(i, ty)) => Some(Constant::Int(-i, ty.clone())),
330	0	(UnOp::Not, Constant::Bool(b)) => Some(Constant::Bool(!b)),
331	0	_ => None,
332		}
333	0	}
334
335		/// Get constant value for an operand
336	0	fn get_constant_value(&self, operand: &Operand) -> Option<Constant> {
337	0	match operand {
338	0	Operand::Constant(c) => Some(c.clone()),
339	0	Operand::Copy(Place::Local(local)) \| Operand::Move(Place::Local(local)) => {
340	0	self.constants.get(local).cloned()
341		}
342	0	_ => None,
343		}
344	0	}
345
346		/// Propagate constants in a statement
347	0	fn propagate_in_statement(&self, stmt: &mut Statement) {
348	0	if let Statement::Assign(_, rvalue) = stmt {
349	0	self.propagate_in_rvalue(rvalue);
350	0	}
351	0	}
352
353		/// Propagate constants in an rvalue
354	0	fn propagate_in_rvalue(&self, rvalue: &mut Rvalue) {
355	0	match rvalue {
356	0	Rvalue::Use(operand) \| Rvalue::UnaryOp(_, operand) => {
357	0	self.propagate_in_operand(operand);
358	0	}
359	0	Rvalue::BinaryOp(_, left, right) => {
360	0	self.propagate_in_operand(left);
361	0	self.propagate_in_operand(right);
362	0	}
363	0	Rvalue::Call(func, args) => {
364	0	self.propagate_in_operand(func);
365	0	for arg in args {
366	0	self.propagate_in_operand(arg);
367	0	}
368		}
369	0	_ => {}
370		}
371	0	}
372
373		/// Propagate constants in an operand
374	0	fn propagate_in_operand(&self, operand: &mut Operand) {
375	0	if let Some(constant) = self.get_constant_value(operand) {
376	0	*operand = Operand::Constant(constant);
377	0	}
378	0	}
379
380		/// Propagate constants in a terminator
381	0	fn propagate_in_terminator(&self, terminator: &mut Terminator) {
382	0	match terminator {
383	0	Terminator::If { condition, .. } => {
384	0	self.propagate_in_operand(condition);
385	0	}
386	0	Terminator::Switch { discriminant, .. } => {
387	0	self.propagate_in_operand(discriminant);
388	0	}
389	0	Terminator::Return(Some(operand)) => {
390	0	self.propagate_in_operand(operand);
391	0	}
392	0	Terminator::Call { func, args, .. } => {
393	0	self.propagate_in_operand(func);
394	0	for arg in args {
395	0	self.propagate_in_operand(arg);
396	0	}
397		}
398	0	_ => {}
399		}
400	0	}
401		}
402
403		/// Common Subexpression Elimination pass
404		pub struct CommonSubexpressionElimination {
405		/// Map from expressions to locals that compute them
406		expressions: HashMap<String, Local>,
407		}
408
409		impl Default for CommonSubexpressionElimination {
410	0	fn default() -> Self {
411	0	Self::new()
412	0	}
413		}
414
415		impl CommonSubexpressionElimination {
416		/// Create a new CSE pass
417		#[must_use]
418	0	pub fn new() -> Self {
419	0	Self {
420	0	expressions: HashMap::new(),
421	0	}
422	0	}
423
424		/// Run CSE on a function
425	0	pub fn run(&mut self, func: &mut Function) {
426	0	self.expressions.clear();
427
428	0	for block in &mut func.blocks {
429	0	for stmt in &mut block.statements {
430	0	self.process_statement(stmt);
431	0	}
432		}
433	0	}
434
435		/// Process a statement for CSE
436	0	fn process_statement(&mut self, stmt: &mut Statement) {
437	0	if let Statement::Assign(Place::Local(local), rvalue) = stmt {
438	0	let expr_key = self.rvalue_key(rvalue);
439
440	0	if let Some(existing_local) = self.expressions.get(&expr_key) {
441	0	// Replace with copy from existing local
442	0	*stmt = Statement::Assign(
443	0	Place::Local(*local),
444	0	Rvalue::Use(Operand::Copy(Place::Local(*existing_local))),
445	0	);
446	0	} else {
447	0	// Record this expression
448	0	self.expressions.insert(expr_key, *local);
449	0	}
450	0	}
451	0	}
452
453		/// Generate a key for an rvalue
454	0	fn rvalue_key(&self, rvalue: &Rvalue) -> String {
455	0	match rvalue {
456	0	Rvalue::Use(operand) => format!("use({})", self.operand_key(operand)),
457	0	Rvalue::BinaryOp(op, left, right) => {
458	0	format!(
459	0	"binop({:?}, {}, {})",
460		op,
461	0	self.operand_key(left),
462	0	self.operand_key(right)
463		)
464		}
465	0	Rvalue::UnaryOp(op, operand) => {
466	0	format!("unop({:?}, {})", op, self.operand_key(operand))
467		}
468	0	_ => format!("{rvalue:?}"), // Fallback
469		}
470	0	}
471
472		/// Generate a key for an operand
473	0	fn operand_key(&self, operand: &Operand) -> String {
474	0	match operand {
475	0	Operand::Copy(place) => format!("copy({})", self.place_key(place)),
476	0	Operand::Move(place) => format!("move({})", self.place_key(place)),
477	0	Operand::Constant(c) => format!("const({c:?})"),
478		}
479	0	}
480
481		/// Generate a key for a place
482		#[allow(clippy::only_used_in_recursion)]
483	0	fn place_key(&self, place: &Place) -> String {
484	0	match place {
485	0	Place::Local(local) => format!("local({})", local.0),
486	0	Place::Field(base, field) => format!("field({}, {})", self.place_key(base), field.0),
487	0	Place::Index(base, index) => {
488	0	format!("index({}, {})", self.place_key(base), self.place_key(index))
489		}
490	0	Place::Deref(base) => format!("deref({})", self.place_key(base)),
491		}
492	0	}
493		}
494
495		/// Run all optimization passes on a function
496	0	pub fn optimize_function(func: &mut Function) {
497	0	let mut dce = DeadCodeElimination::new();
498	0	let mut const_prop = ConstantPropagation::new();
499	0	let mut cse = CommonSubexpressionElimination::new();
500
501		// Run multiple rounds for better results
502	0	for _ in 0..3 {
503	0	const_prop.run(func);
504	0	cse.run(func);
505	0	dce.run(func);
506	0	}
507	0	}
508
509		/// Run all optimization passes on a program
510	0	pub fn optimize_program(program: &mut Program) {
511	0	for function in program.functions.values_mut() {
512	0	optimize_function(function);
513	0	}
514	0	}
515
516		#[cfg(test)]
517		#[allow(clippy::unwrap_used)]
518		mod tests {
519		#[test]
520		fn test_dead_code_elimination() {
521		// Test placeholder - optimization features are framework-level
522		// Implementation deferred pending MIR completion in Phase 2
523		// This test validates that the optimization framework is accessible
524		}
525
526		#[test]
527		fn test_constant_propagation() {
528		// Test placeholder - optimization features are framework-level
529		// Implementation deferred pending MIR completion in Phase 2
530		// This test validates that the optimization framework is accessible
531		}
532
533		#[test]
534		fn test_common_subexpression_elimination() {
535		// Test placeholder - optimization features are framework-level
536		// Implementation deferred pending MIR completion in Phase 2
537		// This test validates that the optimization framework is accessible
538		}
539		}