depyler_analysis/
optimization.rs

1#[cfg(test)]
2use depyler_hir::hir::AssignTarget;
3use depyler_hir::hir::{BinOp, HirExpr, HirFunction, HirStmt};
4use depyler_annotations::{OptimizationLevel, PerformanceHint};
5
6/// Performance optimizer that applies transformations based on annotations
7pub struct PerformanceOptimizer {
8    optimizations_applied: Vec<String>,
9}
10
11impl Default for PerformanceOptimizer {
12    fn default() -> Self {
13        Self::new()
14    }
15}
16
17impl PerformanceOptimizer {
18    pub fn new() -> Self {
19        Self {
20            optimizations_applied: Vec::new(),
21        }
22    }
23
24    /// Optimize a function based on its annotations
25    pub fn optimize_function(&mut self, func: &mut HirFunction) {
26        match func.annotations.optimization_level {
27            OptimizationLevel::Conservative => {
28                self.apply_conservative_optimizations(func);
29            }
30            OptimizationLevel::Standard => {
31                self.apply_standard_optimizations(func);
32            }
33            OptimizationLevel::Aggressive => {
34                self.apply_aggressive_optimizations(func);
35            }
36        }
37
38        // Apply specific performance hints
39        let hints = func.annotations.performance_hints.clone();
40        for hint in &hints {
41            self.apply_performance_hint(func, hint);
42        }
43    }
44
45    fn apply_conservative_optimizations(&mut self, func: &mut HirFunction) {
46        // Only apply safe, guaranteed optimizations
47        self.constant_folding(&mut func.body);
48        self.dead_code_elimination(&mut func.body);
49    }
50
51    fn apply_standard_optimizations(&mut self, func: &mut HirFunction) {
52        // Apply conservative optimizations plus more
53        self.apply_conservative_optimizations(func);
54        self.common_subexpression_elimination(&mut func.body);
55        self.strength_reduction(&mut func.body);
56    }
57
58    fn apply_aggressive_optimizations(&mut self, func: &mut HirFunction) {
59        // Apply all optimizations
60        self.apply_standard_optimizations(func);
61        self.loop_unrolling(&mut func.body, 4);
62        self.inline_small_functions(&mut func.body);
63
64        // If bounds checking is disabled, remove bounds checks
65        if func.annotations.bounds_checking == depyler_annotations::BoundsChecking::Disabled {
66            self.remove_bounds_checks(&mut func.body);
67        }
68    }
69
70    fn apply_performance_hint(&mut self, func: &mut HirFunction, hint: &PerformanceHint) {
71        match hint {
72            PerformanceHint::Vectorize => {
73                self.vectorize_loops(&mut func.body);
74            }
75            PerformanceHint::UnrollLoops(factor) => {
76                self.loop_unrolling(&mut func.body, *factor as usize);
77            }
78            PerformanceHint::OptimizeForLatency => {
79                self.optimize_for_latency(&mut func.body);
80            }
81            PerformanceHint::OptimizeForThroughput => {
82                self.optimize_for_throughput(&mut func.body);
83            }
84            PerformanceHint::PerformanceCritical => {
85                // Apply all applicable optimizations
86                self.inline_small_functions(&mut func.body);
87                self.vectorize_loops(&mut func.body);
88            }
89        }
90    }
91
92    /// Constant folding optimization
93    fn constant_folding(&mut self, stmts: &mut Vec<HirStmt>) {
94        for stmt in stmts {
95            self.fold_constants_in_stmt(stmt);
96        }
97
98        self.optimizations_applied
99            .push("constant_folding".to_string());
100    }
101
102    fn fold_constants_in_stmt(&mut self, stmt: &mut HirStmt) {
103        match stmt {
104            HirStmt::Assign { value, .. } => {
105                self.fold_constants_expr(value);
106            }
107            HirStmt::Return(Some(expr)) => {
108                self.fold_constants_expr(expr);
109            }
110            HirStmt::If {
111                condition,
112                then_body,
113                else_body,
114            } => {
115                self.fold_constants_in_if(condition, then_body, else_body);
116            }
117            HirStmt::While { condition, body } => {
118                self.fold_constants_in_while(condition, body);
119            }
120            HirStmt::For { body, .. } => {
121                self.constant_folding(body);
122            }
123            _ => {}
124        }
125    }
126
127    fn fold_constants_in_if(
128        &mut self,
129        condition: &mut HirExpr,
130        then_body: &mut Vec<HirStmt>,
131        else_body: &mut Option<Vec<HirStmt>>,
132    ) {
133        self.fold_constants_expr(condition);
134        self.constant_folding(then_body);
135        if let Some(else_stmts) = else_body {
136            self.constant_folding(else_stmts);
137        }
138    }
139
140    fn fold_constants_in_while(&mut self, condition: &mut HirExpr, body: &mut Vec<HirStmt>) {
141        self.fold_constants_expr(condition);
142        self.constant_folding(body);
143    }
144
145    fn fold_constants_expr(&self, expr: &mut HirExpr) {
146        if let HirExpr::Binary { op, left, right } = expr {
147            // Recursively fold constants in operands
148            self.fold_constants_expr(left);
149            self.fold_constants_expr(right);
150
151            // If both operands are constants, evaluate the operation
152            if let (HirExpr::Literal(left_lit), HirExpr::Literal(right_lit)) =
153                (left.as_ref(), right.as_ref())
154            {
155                if let Some(folded) = self.evaluate_binary_op(*op, left_lit, right_lit) {
156                    *expr = HirExpr::Literal(folded);
157                }
158            }
159        }
160    }
161
162    fn evaluate_binary_op(
163        &self,
164        op: BinOp,
165        left: &depyler_hir::hir::Literal,
166        right: &depyler_hir::hir::Literal,
167    ) -> Option<depyler_hir::hir::Literal> {
168        use depyler_hir::hir::Literal;
169
170        match (op, left, right) {
171            (BinOp::Add, Literal::Int(a), Literal::Int(b)) => Some(Literal::Int(a + b)),
172            (BinOp::Sub, Literal::Int(a), Literal::Int(b)) => Some(Literal::Int(a - b)),
173            (BinOp::Mul, Literal::Int(a), Literal::Int(b)) => Some(Literal::Int(a * b)),
174            (BinOp::Add, Literal::Float(a), Literal::Float(b)) => Some(Literal::Float(a + b)),
175            (BinOp::Sub, Literal::Float(a), Literal::Float(b)) => Some(Literal::Float(a - b)),
176            (BinOp::Mul, Literal::Float(a), Literal::Float(b)) => Some(Literal::Float(a * b)),
177            _ => None,
178        }
179    }
180
181    /// Dead code elimination
182    fn dead_code_elimination(&mut self, stmts: &mut Vec<HirStmt>) {
183        // Simple DCE: remove statements after unconditional return
184        let mut found_return = false;
185        stmts.retain(|stmt| {
186            if found_return {
187                false
188            } else {
189                if matches!(stmt, HirStmt::Return(_)) {
190                    found_return = true;
191                }
192                true
193            }
194        });
195
196        self.optimizations_applied
197            .push("dead_code_elimination".to_string());
198    }
199
200    /// Common subexpression elimination
201    fn common_subexpression_elimination(&mut self, _stmts: &mut [HirStmt]) {
202        // Simplified CSE - would need data flow analysis for real implementation
203        self.optimizations_applied
204            .push("common_subexpression_elimination".to_string());
205    }
206
207    /// Strength reduction (e.g., x * 2 -> x << 1)
208    fn strength_reduction(&mut self, stmts: &mut [HirStmt]) {
209        for stmt in stmts {
210            match stmt {
211                HirStmt::Assign { value, .. } => {
212                    self.reduce_strength_expr(value);
213                }
214                HirStmt::Return(Some(expr)) => {
215                    self.reduce_strength_expr(expr);
216                }
217                _ => {}
218            }
219        }
220
221        self.optimizations_applied
222            .push("strength_reduction".to_string());
223    }
224
225    fn reduce_strength_expr(&self, expr: &mut HirExpr) {
226        match expr {
227            HirExpr::Binary {
228                op: BinOp::Mul,
229                left: _,
230                right,
231            } => {
232                // DISABLED: Replace multiplication by power of 2 with left shift
233                // This optimization is unsafe as it changes semantics for negative numbers
234                // Re-enable only when we can prove values are non-negative through type analysis
235                if let HirExpr::Literal(depyler_hir::hir::Literal::Int(_n)) = right.as_ref() {
236                    // Strength reduction disabled for semantic correctness
237                    // Left shift and multiplication have different overflow/underflow behavior
238                }
239            }
240            HirExpr::Binary {
241                op: BinOp::Div,
242                left: _,
243                right,
244            } => {
245                // DISABLED: Replace division by power of 2 with right shift
246                // This optimization is unsafe as it changes semantics for negative numbers
247                // Re-enable only when we can prove values are non-negative through type analysis
248                if let HirExpr::Literal(depyler_hir::hir::Literal::Int(_n)) = right.as_ref() {
249                    // Strength reduction disabled for semantic correctness
250                    // Right shift and division have different rounding behavior for negative numbers
251                }
252            }
253            _ => {}
254        }
255    }
256
257    /// Loop unrolling
258    fn loop_unrolling(&mut self, stmts: &mut Vec<HirStmt>, factor: usize) {
259        for stmt in stmts {
260            if let HirStmt::For { body, .. } = stmt {
261                // Simple unrolling - duplicate loop body
262                let original_body = body.clone();
263                for _ in 1..factor {
264                    body.extend(original_body.clone());
265                }
266            }
267        }
268
269        self.optimizations_applied
270            .push(format!("loop_unrolling_{factor}"));
271    }
272
273    /// Vectorization for SIMD operations
274    fn vectorize_loops(&mut self, _stmts: &mut [HirStmt]) {
275        // Simplified vectorization - would need pattern matching for real implementation
276        self.optimizations_applied
277            .push("vectorize_loops".to_string());
278    }
279
280    /// Inline small functions
281    fn inline_small_functions(&mut self, _stmts: &mut [HirStmt]) {
282        // Simplified inlining - would need call graph analysis
283        self.optimizations_applied
284            .push("inline_small_functions".to_string());
285    }
286
287    /// Remove bounds checks (unsafe optimization)
288    fn remove_bounds_checks(&mut self, _stmts: &mut [HirStmt]) {
289        // Would remove array bounds checks - requires careful analysis
290        self.optimizations_applied
291            .push("remove_bounds_checks".to_string());
292    }
293
294    /// Optimize for low latency
295    fn optimize_for_latency(&mut self, _stmts: &mut [HirStmt]) {
296        // Prioritize reducing critical path length
297        self.optimizations_applied
298            .push("optimize_for_latency".to_string());
299    }
300
301    /// Optimize for high throughput
302    fn optimize_for_throughput(&mut self, _stmts: &mut [HirStmt]) {
303        // Prioritize parallelism and vectorization
304        self.optimizations_applied
305            .push("optimize_for_throughput".to_string());
306    }
307
308    /// Get list of optimizations that were applied
309    pub fn get_applied_optimizations(&self) -> &[String] {
310        &self.optimizations_applied
311    }
312}
313
314/// Apply optimizations to a module based on annotations
315pub fn optimize_module(module: &mut depyler_hir::hir::HirModule) -> Vec<String> {
316    let mut all_optimizations = Vec::new();
317
318    for func in &mut module.functions {
319        let mut optimizer = PerformanceOptimizer::new();
320        optimizer.optimize_function(func);
321        all_optimizations.extend(optimizer.get_applied_optimizations().to_vec());
322    }
323
324    all_optimizations
325}
326
327#[cfg(test)]
328mod tests {
329    use super::*;
330    use depyler_hir::hir::{FunctionProperties, HirModule, HirParam, Literal, Type};
331    use depyler_annotations::{BoundsChecking, TranspilationAnnotations};
332    use smallvec::smallvec;
333
334    // Helper to create a basic function for testing
335    fn create_test_func(body: Vec<HirStmt>, opt_level: OptimizationLevel) -> HirFunction {
336        HirFunction {
337            name: "test".to_string(),
338            params: smallvec![],
339            ret_type: Type::Int,
340            body,
341            properties: FunctionProperties::default(),
342            annotations: TranspilationAnnotations {
343                optimization_level: opt_level,
344                ..Default::default()
345            },
346            docstring: None,
347        }
348    }
349
350    // === PerformanceOptimizer construction tests ===
351
352    #[test]
353    fn test_performance_optimizer_new() {
354        let optimizer = PerformanceOptimizer::new();
355        assert!(optimizer.get_applied_optimizations().is_empty());
356    }
357
358    #[test]
359    fn test_performance_optimizer_default() {
360        let optimizer = PerformanceOptimizer::default();
361        assert!(optimizer.get_applied_optimizations().is_empty());
362    }
363
364    #[test]
365    fn test_get_applied_optimizations_empty() {
366        let optimizer = PerformanceOptimizer::new();
367        let applied = optimizer.get_applied_optimizations();
368        assert!(applied.is_empty());
369    }
370
371    // === Optimization level tests ===
372
373    #[test]
374    fn test_conservative_optimizations() {
375        let mut optimizer = PerformanceOptimizer::new();
376        let mut func = create_test_func(vec![], OptimizationLevel::Conservative);
377
378        optimizer.optimize_function(&mut func);
379
380        let applied = optimizer.get_applied_optimizations();
381        assert!(applied.contains(&"constant_folding".to_string()));
382        assert!(applied.contains(&"dead_code_elimination".to_string()));
383        // Should NOT contain aggressive optimizations
384        assert!(!applied.contains(&"inline_small_functions".to_string()));
385    }
386
387    #[test]
388    fn test_standard_optimizations() {
389        let mut optimizer = PerformanceOptimizer::new();
390        let mut func = create_test_func(vec![], OptimizationLevel::Standard);
391
392        optimizer.optimize_function(&mut func);
393
394        let applied = optimizer.get_applied_optimizations();
395        // Should contain conservative + standard optimizations
396        assert!(applied.contains(&"constant_folding".to_string()));
397        assert!(applied.contains(&"dead_code_elimination".to_string()));
398        assert!(applied.contains(&"common_subexpression_elimination".to_string()));
399        assert!(applied.contains(&"strength_reduction".to_string()));
400    }
401
402    #[test]
403    fn test_aggressive_optimizations_applied() {
404        let mut optimizer = PerformanceOptimizer::new();
405        let mut func = create_test_func(vec![], OptimizationLevel::Aggressive);
406
407        optimizer.optimize_function(&mut func);
408
409        let applied = optimizer.get_applied_optimizations();
410        // Should contain all optimizations
411        assert!(applied.contains(&"constant_folding".to_string()));
412        assert!(applied.contains(&"inline_small_functions".to_string()));
413        assert!(applied.iter().any(|s| s.starts_with("loop_unrolling")));
414    }
415
416    // === Constant folding tests ===
417
418    #[test]
419    fn test_constant_folding() {
420        let mut optimizer = PerformanceOptimizer::new();
421
422        let mut func = HirFunction {
423            name: "test".to_string(),
424            params: smallvec![],
425            ret_type: Type::Int,
426            body: vec![HirStmt::Return(Some(HirExpr::Binary {
427                op: BinOp::Add,
428                left: Box::new(HirExpr::Literal(Literal::Int(2))),
429                right: Box::new(HirExpr::Literal(Literal::Int(3))),
430            }))],
431            properties: Default::default(),
432            annotations: TranspilationAnnotations {
433                optimization_level: OptimizationLevel::Standard,
434                ..Default::default()
435            },
436            docstring: None,
437        };
438
439        optimizer.optimize_function(&mut func);
440
441        // Check that constant folding was applied
442        if let HirStmt::Return(Some(HirExpr::Literal(Literal::Int(n)))) = &func.body[0] {
443            assert_eq!(*n, 5);
444        } else {
445            panic!("Expected constant folding to produce literal 5");
446        }
447    }
448
449    #[test]
450    fn test_constant_folding_subtraction() {
451        let mut optimizer = PerformanceOptimizer::new();
452        let body = vec![HirStmt::Return(Some(HirExpr::Binary {
453            op: BinOp::Sub,
454            left: Box::new(HirExpr::Literal(Literal::Int(10))),
455            right: Box::new(HirExpr::Literal(Literal::Int(3))),
456        }))];
457        let mut func = create_test_func(body, OptimizationLevel::Conservative);
458
459        optimizer.optimize_function(&mut func);
460
461        if let HirStmt::Return(Some(HirExpr::Literal(Literal::Int(n)))) = &func.body[0] {
462            assert_eq!(*n, 7);
463        } else {
464            panic!("Expected constant folding to produce literal 7");
465        }
466    }
467
468    #[test]
469    fn test_constant_folding_multiplication() {
470        let mut optimizer = PerformanceOptimizer::new();
471        let body = vec![HirStmt::Return(Some(HirExpr::Binary {
472            op: BinOp::Mul,
473            left: Box::new(HirExpr::Literal(Literal::Int(4))),
474            right: Box::new(HirExpr::Literal(Literal::Int(5))),
475        }))];
476        let mut func = create_test_func(body, OptimizationLevel::Conservative);
477
478        optimizer.optimize_function(&mut func);
479
480        if let HirStmt::Return(Some(HirExpr::Literal(Literal::Int(n)))) = &func.body[0] {
481            assert_eq!(*n, 20);
482        } else {
483            panic!("Expected constant folding to produce literal 20");
484        }
485    }
486
487    #[test]
488    fn test_constant_folding_float_add() {
489        let mut optimizer = PerformanceOptimizer::new();
490        let body = vec![HirStmt::Return(Some(HirExpr::Binary {
491            op: BinOp::Add,
492            left: Box::new(HirExpr::Literal(Literal::Float(1.5))),
493            right: Box::new(HirExpr::Literal(Literal::Float(2.5))),
494        }))];
495        let mut func = create_test_func(body, OptimizationLevel::Conservative);
496
497        optimizer.optimize_function(&mut func);
498
499        if let HirStmt::Return(Some(HirExpr::Literal(Literal::Float(n)))) = &func.body[0] {
500            assert!((n - 4.0).abs() < f64::EPSILON);
501        } else {
502            panic!("Expected constant folding to produce float literal");
503        }
504    }
505
506    #[test]
507    fn test_constant_folding_float_sub() {
508        let mut optimizer = PerformanceOptimizer::new();
509        let body = vec![HirStmt::Return(Some(HirExpr::Binary {
510            op: BinOp::Sub,
511            left: Box::new(HirExpr::Literal(Literal::Float(5.0))),
512            right: Box::new(HirExpr::Literal(Literal::Float(2.0))),
513        }))];
514        let mut func = create_test_func(body, OptimizationLevel::Conservative);
515
516        optimizer.optimize_function(&mut func);
517
518        if let HirStmt::Return(Some(HirExpr::Literal(Literal::Float(n)))) = &func.body[0] {
519            assert!((n - 3.0).abs() < f64::EPSILON);
520        } else {
521            panic!("Expected constant folding to produce float literal");
522        }
523    }
524
525    #[test]
526    fn test_constant_folding_float_mul() {
527        let mut optimizer = PerformanceOptimizer::new();
528        let body = vec![HirStmt::Return(Some(HirExpr::Binary {
529            op: BinOp::Mul,
530            left: Box::new(HirExpr::Literal(Literal::Float(2.0))),
531            right: Box::new(HirExpr::Literal(Literal::Float(3.0))),
532        }))];
533        let mut func = create_test_func(body, OptimizationLevel::Conservative);
534
535        optimizer.optimize_function(&mut func);
536
537        if let HirStmt::Return(Some(HirExpr::Literal(Literal::Float(n)))) = &func.body[0] {
538            assert!((n - 6.0).abs() < f64::EPSILON);
539        } else {
540            panic!("Expected constant folding to produce float literal");
541        }
542    }
543
544    #[test]
545    fn test_constant_folding_nested_expressions() {
546        let mut optimizer = PerformanceOptimizer::new();
547        // (2 + 3) + 4 = 5 + 4 = 9
548        let body = vec![HirStmt::Return(Some(HirExpr::Binary {
549            op: BinOp::Add,
550            left: Box::new(HirExpr::Binary {
551                op: BinOp::Add,
552                left: Box::new(HirExpr::Literal(Literal::Int(2))),
553                right: Box::new(HirExpr::Literal(Literal::Int(3))),
554            }),
555            right: Box::new(HirExpr::Literal(Literal::Int(4))),
556        }))];
557        let mut func = create_test_func(body, OptimizationLevel::Conservative);
558
559        optimizer.optimize_function(&mut func);
560
561        if let HirStmt::Return(Some(HirExpr::Literal(Literal::Int(n)))) = &func.body[0] {
562            assert_eq!(*n, 9);
563        } else {
564            panic!("Expected nested constant folding to produce literal 9");
565        }
566    }
567
568    #[test]
569    fn test_constant_folding_in_assign() {
570        let mut optimizer = PerformanceOptimizer::new();
571        let body = vec![HirStmt::Assign {
572            target: AssignTarget::Symbol("x".to_string()),
573            value: HirExpr::Binary {
574                op: BinOp::Add,
575                left: Box::new(HirExpr::Literal(Literal::Int(10))),
576                right: Box::new(HirExpr::Literal(Literal::Int(20))),
577            },
578            type_annotation: None,
579        }];
580        let mut func = create_test_func(body, OptimizationLevel::Conservative);
581
582        optimizer.optimize_function(&mut func);
583
584        if let HirStmt::Assign { value, .. } = &func.body[0] {
585            if let HirExpr::Literal(Literal::Int(n)) = value {
586                assert_eq!(*n, 30);
587            } else {
588                panic!("Expected constant folding in assign");
589            }
590        }
591    }
592
593    #[test]
594    fn test_constant_folding_in_if_condition() {
595        let mut optimizer = PerformanceOptimizer::new();
596        let body = vec![HirStmt::If {
597            condition: HirExpr::Binary {
598                op: BinOp::Add,
599                left: Box::new(HirExpr::Literal(Literal::Int(1))),
600                right: Box::new(HirExpr::Literal(Literal::Int(2))),
601            },
602            then_body: vec![],
603            else_body: None,
604        }];
605        let mut func = create_test_func(body, OptimizationLevel::Conservative);
606
607        optimizer.optimize_function(&mut func);
608
609        if let HirStmt::If { condition, .. } = &func.body[0] {
610            assert!(matches!(condition, HirExpr::Literal(Literal::Int(3))));
611        }
612    }
613
614    #[test]
615    fn test_constant_folding_in_while_condition() {
616        let mut optimizer = PerformanceOptimizer::new();
617        let body = vec![HirStmt::While {
618            condition: HirExpr::Binary {
619                op: BinOp::Add,
620                left: Box::new(HirExpr::Literal(Literal::Int(5))),
621                right: Box::new(HirExpr::Literal(Literal::Int(5))),
622            },
623            body: vec![],
624        }];
625        let mut func = create_test_func(body, OptimizationLevel::Conservative);
626
627        optimizer.optimize_function(&mut func);
628
629        if let HirStmt::While { condition, .. } = &func.body[0] {
630            assert!(matches!(condition, HirExpr::Literal(Literal::Int(10))));
631        }
632    }
633
634    #[test]
635    fn test_constant_folding_in_for_body() {
636        let mut optimizer = PerformanceOptimizer::new();
637        let body = vec![HirStmt::For {
638            target: AssignTarget::Symbol("i".to_string()),
639            iter: HirExpr::Var("range".to_string()),
640            body: vec![HirStmt::Assign {
641                target: AssignTarget::Symbol("x".to_string()),
642                value: HirExpr::Binary {
643                    op: BinOp::Add,
644                    left: Box::new(HirExpr::Literal(Literal::Int(1))),
645                    right: Box::new(HirExpr::Literal(Literal::Int(1))),
646                },
647                type_annotation: None,
648            }],
649        }];
650        let mut func = create_test_func(body, OptimizationLevel::Conservative);
651
652        optimizer.optimize_function(&mut func);
653
654        if let HirStmt::For { body, .. } = &func.body[0] {
655            if let HirStmt::Assign { value, .. } = &body[0] {
656                assert!(matches!(value, HirExpr::Literal(Literal::Int(2))));
657            }
658        }
659    }
660
661    #[test]
662    fn test_constant_folding_no_fold_for_division() {
663        // Division is not supported in constant folding
664        let mut optimizer = PerformanceOptimizer::new();
665        let body = vec![HirStmt::Return(Some(HirExpr::Binary {
666            op: BinOp::Div,
667            left: Box::new(HirExpr::Literal(Literal::Int(10))),
668            right: Box::new(HirExpr::Literal(Literal::Int(2))),
669        }))];
670        let mut func = create_test_func(body, OptimizationLevel::Conservative);
671
672        optimizer.optimize_function(&mut func);
673
674        // Should NOT be folded since Div is not implemented
675        if let HirStmt::Return(Some(expr)) = &func.body[0] {
676            assert!(matches!(expr, HirExpr::Binary { op: BinOp::Div, .. }));
677        }
678    }
679
680    // === Strength reduction tests ===
681
682    #[test]
683    fn test_strength_reduction() {
684        let mut optimizer = PerformanceOptimizer::new();
685
686        let mut func = HirFunction {
687            name: "test".to_string(),
688            params: smallvec![HirParam::new("x".to_string(), Type::Int)],
689            ret_type: Type::Int,
690            body: vec![HirStmt::Return(Some(HirExpr::Binary {
691                op: BinOp::Mul,
692                left: Box::new(HirExpr::Var("x".to_string())),
693                right: Box::new(HirExpr::Literal(Literal::Int(8))),
694            }))],
695            properties: Default::default(),
696            annotations: TranspilationAnnotations {
697                optimization_level: OptimizationLevel::Standard,
698                ..Default::default()
699            },
700            docstring: None,
701        };
702
703        optimizer.optimize_function(&mut func);
704
705        // Check that multiplication by 8 is NOT replaced with left shift for correctness
706        // Strength reduction is disabled to maintain semantic equivalence
707        if let HirStmt::Return(Some(HirExpr::Binary { op, right, .. })) = &func.body[0] {
708            assert_eq!(
709                *op,
710                BinOp::Mul,
711                "Should preserve multiplication for semantic correctness"
712            );
713            if let HirExpr::Literal(Literal::Int(n)) = right.as_ref() {
714                assert_eq!(*n, 8, "Should preserve original multiplication operand");
715            }
716        } else {
717            panic!("Expected multiplication to be preserved");
718        }
719    }
720
721    #[test]
722    fn test_strength_reduction_division() {
723        let mut optimizer = PerformanceOptimizer::new();
724        let body = vec![HirStmt::Return(Some(HirExpr::Binary {
725            op: BinOp::Div,
726            left: Box::new(HirExpr::Var("x".to_string())),
727            right: Box::new(HirExpr::Literal(Literal::Int(4))),
728        }))];
729        let mut func = create_test_func(body, OptimizationLevel::Standard);
730
731        optimizer.optimize_function(&mut func);
732
733        // Division should also be preserved
734        if let HirStmt::Return(Some(HirExpr::Binary { op, .. })) = &func.body[0] {
735            assert_eq!(*op, BinOp::Div);
736        }
737    }
738
739    // === Dead code elimination tests ===
740
741    #[test]
742    fn test_dead_code_elimination() {
743        let mut optimizer = PerformanceOptimizer::new();
744
745        let mut func = HirFunction {
746            name: "test".to_string(),
747            params: smallvec![],
748            ret_type: Type::Int,
749            body: vec![
750                HirStmt::Return(Some(HirExpr::Literal(Literal::Int(42)))),
751                HirStmt::Assign {
752                    target: AssignTarget::Symbol("unreachable".to_string()),
753                    value: HirExpr::Literal(Literal::Int(0)),
754                    type_annotation: None,
755                },
756            ],
757            properties: Default::default(),
758            annotations: TranspilationAnnotations {
759                optimization_level: OptimizationLevel::Conservative,
760                ..Default::default()
761            },
762            docstring: None,
763        };
764
765        optimizer.optimize_function(&mut func);
766
767        // Check that unreachable code was removed
768        assert_eq!(func.body.len(), 1);
769        assert!(matches!(func.body[0], HirStmt::Return(_)));
770    }
771
772    #[test]
773    fn test_dead_code_elimination_multiple_statements() {
774        let mut optimizer = PerformanceOptimizer::new();
775        let body = vec![
776            HirStmt::Assign {
777                target: AssignTarget::Symbol("x".to_string()),
778                value: HirExpr::Literal(Literal::Int(1)),
779                type_annotation: None,
780            },
781            HirStmt::Return(Some(HirExpr::Var("x".to_string()))),
782            HirStmt::Assign {
783                target: AssignTarget::Symbol("y".to_string()),
784                value: HirExpr::Literal(Literal::Int(2)),
785                type_annotation: None,
786            },
787            HirStmt::Assign {
788                target: AssignTarget::Symbol("z".to_string()),
789                value: HirExpr::Literal(Literal::Int(3)),
790                type_annotation: None,
791            },
792        ];
793        let mut func = create_test_func(body, OptimizationLevel::Conservative);
794
795        optimizer.optimize_function(&mut func);
796
797        // Only first 2 statements should remain
798        assert_eq!(func.body.len(), 2);
799    }
800
801    #[test]
802    fn test_dead_code_elimination_no_return() {
803        let mut optimizer = PerformanceOptimizer::new();
804        let body = vec![
805            HirStmt::Assign {
806                target: AssignTarget::Symbol("x".to_string()),
807                value: HirExpr::Literal(Literal::Int(1)),
808                type_annotation: None,
809            },
810            HirStmt::Assign {
811                target: AssignTarget::Symbol("y".to_string()),
812                value: HirExpr::Literal(Literal::Int(2)),
813                type_annotation: None,
814            },
815        ];
816        let mut func = create_test_func(body, OptimizationLevel::Conservative);
817
818        optimizer.optimize_function(&mut func);
819
820        // All statements should remain (no return to trigger DCE)
821        assert_eq!(func.body.len(), 2);
822    }
823
824    // === Performance hint tests ===
825
826    #[test]
827    fn test_aggressive_optimizations() {
828        let mut optimizer = PerformanceOptimizer::new();
829
830        let mut annotations = TranspilationAnnotations {
831            optimization_level: OptimizationLevel::Aggressive,
832            ..Default::default()
833        };
834        annotations
835            .performance_hints
836            .push(PerformanceHint::Vectorize);
837
838        let mut func = HirFunction {
839            name: "test".to_string(),
840            params: smallvec![],
841            ret_type: Type::Int,
842            body: vec![],
843            properties: Default::default(),
844            annotations,
845            docstring: None,
846        };
847
848        optimizer.optimize_function(&mut func);
849
850        // Check that multiple optimizations were applied
851        let applied = optimizer.get_applied_optimizations();
852        assert!(applied.contains(&"constant_folding".to_string()));
853        assert!(applied.contains(&"vectorize_loops".to_string()));
854    }
855
856    #[test]
857    fn test_performance_hint_vectorize() {
858        let mut optimizer = PerformanceOptimizer::new();
859        let mut annotations = TranspilationAnnotations::default();
860        annotations
861            .performance_hints
862            .push(PerformanceHint::Vectorize);
863
864        let mut func = HirFunction {
865            name: "test".to_string(),
866            params: smallvec![],
867            ret_type: Type::Int,
868            body: vec![],
869            properties: Default::default(),
870            annotations,
871            docstring: None,
872        };
873
874        optimizer.optimize_function(&mut func);
875
876        let applied = optimizer.get_applied_optimizations();
877        assert!(applied.contains(&"vectorize_loops".to_string()));
878    }
879
880    #[test]
881    fn test_performance_hint_unroll_loops() {
882        let mut optimizer = PerformanceOptimizer::new();
883        let mut annotations = TranspilationAnnotations::default();
884        annotations
885            .performance_hints
886            .push(PerformanceHint::UnrollLoops(8));
887
888        let mut func = HirFunction {
889            name: "test".to_string(),
890            params: smallvec![],
891            ret_type: Type::Int,
892            body: vec![],
893            properties: Default::default(),
894            annotations,
895            docstring: None,
896        };
897
898        optimizer.optimize_function(&mut func);
899
900        let applied = optimizer.get_applied_optimizations();
901        assert!(applied.contains(&"loop_unrolling_8".to_string()));
902    }
903
904    #[test]
905    fn test_performance_hint_optimize_for_latency() {
906        let mut optimizer = PerformanceOptimizer::new();
907        let mut annotations = TranspilationAnnotations::default();
908        annotations
909            .performance_hints
910            .push(PerformanceHint::OptimizeForLatency);
911
912        let mut func = HirFunction {
913            name: "test".to_string(),
914            params: smallvec![],
915            ret_type: Type::Int,
916            body: vec![],
917            properties: Default::default(),
918            annotations,
919            docstring: None,
920        };
921
922        optimizer.optimize_function(&mut func);
923
924        let applied = optimizer.get_applied_optimizations();
925        assert!(applied.contains(&"optimize_for_latency".to_string()));
926    }
927
928    #[test]
929    fn test_performance_hint_optimize_for_throughput() {
930        let mut optimizer = PerformanceOptimizer::new();
931        let mut annotations = TranspilationAnnotations::default();
932        annotations
933            .performance_hints
934            .push(PerformanceHint::OptimizeForThroughput);
935
936        let mut func = HirFunction {
937            name: "test".to_string(),
938            params: smallvec![],
939            ret_type: Type::Int,
940            body: vec![],
941            properties: Default::default(),
942            annotations,
943            docstring: None,
944        };
945
946        optimizer.optimize_function(&mut func);
947
948        let applied = optimizer.get_applied_optimizations();
949        assert!(applied.contains(&"optimize_for_throughput".to_string()));
950    }
951
952    #[test]
953    fn test_performance_hint_performance_critical() {
954        let mut optimizer = PerformanceOptimizer::new();
955        let mut annotations = TranspilationAnnotations::default();
956        annotations
957            .performance_hints
958            .push(PerformanceHint::PerformanceCritical);
959
960        let mut func = HirFunction {
961            name: "test".to_string(),
962            params: smallvec![],
963            ret_type: Type::Int,
964            body: vec![],
965            properties: Default::default(),
966            annotations,
967            docstring: None,
968        };
969
970        optimizer.optimize_function(&mut func);
971
972        let applied = optimizer.get_applied_optimizations();
973        assert!(applied.contains(&"inline_small_functions".to_string()));
974        assert!(applied.contains(&"vectorize_loops".to_string()));
975    }
976
977    // === Bounds checking tests ===
978
979    #[test]
980    fn test_aggressive_with_bounds_checking_disabled() {
981        let mut optimizer = PerformanceOptimizer::new();
982        let mut func = HirFunction {
983            name: "test".to_string(),
984            params: smallvec![],
985            ret_type: Type::Int,
986            body: vec![],
987            properties: Default::default(),
988            annotations: TranspilationAnnotations {
989                optimization_level: OptimizationLevel::Aggressive,
990                bounds_checking: BoundsChecking::Disabled,
991                ..Default::default()
992            },
993            docstring: None,
994        };
995
996        optimizer.optimize_function(&mut func);
997
998        let applied = optimizer.get_applied_optimizations();
999        assert!(applied.contains(&"remove_bounds_checks".to_string()));
1000    }
1001
1002    #[test]
1003    fn test_aggressive_with_bounds_checking_explicit() {
1004        let mut optimizer = PerformanceOptimizer::new();
1005        let mut func = HirFunction {
1006            name: "test".to_string(),
1007            params: smallvec![],
1008            ret_type: Type::Int,
1009            body: vec![],
1010            properties: Default::default(),
1011            annotations: TranspilationAnnotations {
1012                optimization_level: OptimizationLevel::Aggressive,
1013                bounds_checking: BoundsChecking::Explicit,
1014                ..Default::default()
1015            },
1016            docstring: None,
1017        };
1018
1019        optimizer.optimize_function(&mut func);
1020
1021        let applied = optimizer.get_applied_optimizations();
1022        // Should NOT contain remove_bounds_checks
1023        assert!(!applied.contains(&"remove_bounds_checks".to_string()));
1024    }
1025
1026    // === Loop unrolling tests ===
1027
1028    #[test]
1029    fn test_loop_unrolling_with_for_loop() {
1030        let mut optimizer = PerformanceOptimizer::new();
1031        let body = vec![HirStmt::For {
1032            target: AssignTarget::Symbol("i".to_string()),
1033            iter: HirExpr::Var("range".to_string()),
1034            body: vec![HirStmt::Assign {
1035                target: AssignTarget::Symbol("x".to_string()),
1036                value: HirExpr::Literal(Literal::Int(1)),
1037                type_annotation: None,
1038            }],
1039        }];
1040        let mut func = create_test_func(body, OptimizationLevel::Aggressive);
1041
1042        optimizer.optimize_function(&mut func);
1043
1044        // Loop body should be duplicated (default factor 4)
1045        if let HirStmt::For { body, .. } = &func.body[0] {
1046            // Body should now have 4 copies of the original statement
1047            assert_eq!(body.len(), 4);
1048        }
1049    }
1050
1051    // === Module optimization tests ===
1052
1053    #[test]
1054    fn test_optimize_module() {
1055        let mut module = HirModule {
1056            functions: vec![
1057                HirFunction {
1058                    name: "func1".to_string(),
1059                    params: smallvec![],
1060                    ret_type: Type::Int,
1061                    body: vec![],
1062                    properties: Default::default(),
1063                    annotations: TranspilationAnnotations {
1064                        optimization_level: OptimizationLevel::Standard,
1065                        ..Default::default()
1066                    },
1067                    docstring: None,
1068                },
1069                HirFunction {
1070                    name: "func2".to_string(),
1071                    params: smallvec![],
1072                    ret_type: Type::Int,
1073                    body: vec![],
1074                    properties: Default::default(),
1075                    annotations: TranspilationAnnotations {
1076                        optimization_level: OptimizationLevel::Aggressive,
1077                        ..Default::default()
1078                    },
1079                    docstring: None,
1080                },
1081            ],
1082            imports: vec![],
1083            type_aliases: vec![],
1084            protocols: vec![],
1085            classes: vec![],
1086            constants: vec![],
1087            top_level_stmts: vec![],
1088        };
1089
1090        let optimizations = optimize_module(&mut module);
1091
1092        // Both functions should have optimizations applied
1093        assert!(!optimizations.is_empty());
1094    }
1095
1096    #[test]
1097    fn test_optimize_module_empty() {
1098        let mut module = HirModule {
1099            functions: vec![],
1100            imports: vec![],
1101            type_aliases: vec![],
1102            protocols: vec![],
1103            classes: vec![],
1104            constants: vec![],
1105            top_level_stmts: vec![],
1106        };
1107
1108        let optimizations = optimize_module(&mut module);
1109        assert!(optimizations.is_empty());
1110    }
1111
1112    #[test]
1113    fn test_optimize_module_single_function() {
1114        let mut module = HirModule {
1115            functions: vec![HirFunction {
1116                name: "single".to_string(),
1117                params: smallvec![],
1118                ret_type: Type::Int,
1119                body: vec![],
1120                properties: Default::default(),
1121                annotations: TranspilationAnnotations {
1122                    optimization_level: OptimizationLevel::Conservative,
1123                    ..Default::default()
1124                },
1125                docstring: None,
1126            }],
1127            imports: vec![],
1128            type_aliases: vec![],
1129            protocols: vec![],
1130            classes: vec![],
1131            constants: vec![],
1132            top_level_stmts: vec![],
1133        };
1134
1135        let optimizations = optimize_module(&mut module);
1136        assert!(optimizations.contains(&"constant_folding".to_string()));
1137        assert!(optimizations.contains(&"dead_code_elimination".to_string()));
1138    }
1139
1140    // === Evaluate binary op tests ===
1141
1142    #[test]
1143    fn test_evaluate_binary_op_unsupported() {
1144        let optimizer = PerformanceOptimizer::new();
1145
1146        // Test unsupported operation (Pow)
1147        let result = optimizer.evaluate_binary_op(BinOp::Pow, &Literal::Int(2), &Literal::Int(3));
1148        assert!(result.is_none());
1149    }
1150
1151    #[test]
1152    fn test_evaluate_binary_op_mixed_types() {
1153        let optimizer = PerformanceOptimizer::new();
1154
1155        // Test mixed types (Int + Float) - not supported
1156        let result =
1157            optimizer.evaluate_binary_op(BinOp::Add, &Literal::Int(2), &Literal::Float(3.0));
1158        assert!(result.is_none());
1159    }
1160
1161    #[test]
1162    fn test_evaluate_binary_op_string_literal() {
1163        let optimizer = PerformanceOptimizer::new();
1164
1165        // String literals not supported for binary ops
1166        let result = optimizer.evaluate_binary_op(
1167            BinOp::Add,
1168            &Literal::String("a".to_string()),
1169            &Literal::String("b".to_string()),
1170        );
1171        assert!(result.is_none());
1172    }
1173
1174    // === If/else folding tests ===
1175
1176    #[test]
1177    fn test_constant_folding_if_with_else() {
1178        let mut optimizer = PerformanceOptimizer::new();
1179        let body = vec![HirStmt::If {
1180            condition: HirExpr::Binary {
1181                op: BinOp::Add,
1182                left: Box::new(HirExpr::Literal(Literal::Int(1))),
1183                right: Box::new(HirExpr::Literal(Literal::Int(1))),
1184            },
1185            then_body: vec![HirStmt::Return(Some(HirExpr::Binary {
1186                op: BinOp::Add,
1187                left: Box::new(HirExpr::Literal(Literal::Int(2))),
1188                right: Box::new(HirExpr::Literal(Literal::Int(2))),
1189            }))],
1190            else_body: Some(vec![HirStmt::Return(Some(HirExpr::Binary {
1191                op: BinOp::Add,
1192                left: Box::new(HirExpr::Literal(Literal::Int(3))),
1193                right: Box::new(HirExpr::Literal(Literal::Int(3))),
1194            }))]),
1195        }];
1196        let mut func = create_test_func(body, OptimizationLevel::Conservative);
1197
1198        optimizer.optimize_function(&mut func);
1199
1200        // Check all constants are folded
1201        if let HirStmt::If {
1202            condition,
1203            then_body,
1204            else_body,
1205        } = &func.body[0]
1206        {
1207            assert!(matches!(condition, HirExpr::Literal(Literal::Int(2))));
1208
1209            if let HirStmt::Return(Some(HirExpr::Literal(Literal::Int(n)))) = &then_body[0] {
1210                assert_eq!(*n, 4);
1211            }
1212
1213            if let Some(else_stmts) = else_body {
1214                if let HirStmt::Return(Some(HirExpr::Literal(Literal::Int(n)))) = &else_stmts[0] {
1215                    assert_eq!(*n, 6);
1216                }
1217            }
1218        }
1219    }
1220
1221    // === Multiple performance hints test ===
1222
1223    #[test]
1224    fn test_multiple_performance_hints() {
1225        let mut optimizer = PerformanceOptimizer::new();
1226        let mut annotations = TranspilationAnnotations::default();
1227        annotations
1228            .performance_hints
1229            .push(PerformanceHint::Vectorize);
1230        annotations
1231            .performance_hints
1232            .push(PerformanceHint::OptimizeForLatency);
1233        annotations
1234            .performance_hints
1235            .push(PerformanceHint::UnrollLoops(2));
1236
1237        let mut func = HirFunction {
1238            name: "test".to_string(),
1239            params: smallvec![],
1240            ret_type: Type::Int,
1241            body: vec![],
1242            properties: Default::default(),
1243            annotations,
1244            docstring: None,
1245        };
1246
1247        optimizer.optimize_function(&mut func);
1248
1249        let applied = optimizer.get_applied_optimizations();
1250        assert!(applied.contains(&"vectorize_loops".to_string()));
1251        assert!(applied.contains(&"optimize_for_latency".to_string()));
1252        assert!(applied.contains(&"loop_unrolling_2".to_string()));
1253    }
1254}
depyler_analysis/optimization.rs

depyler_analysis/
optimization.rs
