ryna/
optimization.rs

1use rustc_hash::{FxHashMap, FxHashSet};
2use malachite::Integer;
3
4use crate::{compilation::{CompiledRynaExpr, RynaInstruction}, context::RynaContext, integer_ext::{is_valid_index, to_usize, ONE}, object::Object, operations::{ADD_BINOP_ID, ASSIGN_BINOP_ID, DEREF_UNOP_ID, DIV_BINOP_ID, MOD_BINOP_ID, MUL_BINOP_ID, NEG_UNOP_ID, SHL_BINOP_ID, SUB_BINOP_ID}, parser::{Location, RynaExpr}, types::{Type, FLOAT, INT}};
5
6/*
7    ╒═══════════════════════════╕
8    │ Syntax tree optimizations │
9    ╘═══════════════════════════╛
10*/
11
12const INLINE_THRESHOLD: f32 = 50.0;
13
14lazy_static! {
15    pub static ref CONST_UNOP_IDS: FxHashSet<usize> = [NEG_UNOP_ID].iter().cloned().collect();
16    pub static ref CONST_BINOP_IDS: FxHashSet<usize> = [ADD_BINOP_ID, SUB_BINOP_ID, MUL_BINOP_ID, DIV_BINOP_ID, MOD_BINOP_ID].iter().copied().collect();
17    pub static ref CONST_NARYOP_IDS: FxHashSet<usize> = [].iter().copied().collect();
18    pub static ref CONST_FUNC_IDS: FxHashSet<usize> = [].iter().copied().collect();
19}
20
21impl RynaContext {
22    pub fn count_usages_expr(expr: &RynaExpr, var_usages: &mut FxHashMap<usize, usize>, offset: usize) {
23        match expr {
24            RynaExpr::Variable(_, id, _, _, g) => {
25                *var_usages.entry(*id).or_default() += offset + (*g as usize); // Never move global variables
26            },
27
28            RynaExpr::UnaryOperation(_, _, _, e) |
29            RynaExpr::AttributeAccess(_, e, _) |
30            RynaExpr::Return(_, e) |
31            RynaExpr::CompiledVariableDefinition(_, _, _, _, e, _) |
32            RynaExpr::CompiledVariableAssignment(_, _, _, _, e, _) => RynaContext::count_usages_expr(e, var_usages, offset),
33
34            RynaExpr::CompiledLambda(_, _, c, _, _, _) => {
35                for (_, e) in c {
36                    RynaContext::count_usages_expr(e, var_usages, 2); // Set offset of 2 in order not to insert moves inside captures
37                }
38            }
39
40            RynaExpr::DoBlock(_, exprs, _) |
41            RynaExpr::FunctionCall(_, _, _, exprs) |
42            RynaExpr::Tuple(_, exprs) => {
43                for e in exprs {
44                    RynaContext::count_usages_expr(e, var_usages, offset);
45                }
46            },
47
48            RynaExpr::CompiledFor(_, _, _, _, c, exprs) |
49            RynaExpr::While(_, c, exprs) => {
50                RynaContext::count_usages_expr(c, var_usages, offset); // Set offset of 2 in order not to insert moves inside loops
51
52                for e in exprs {
53                    RynaContext::count_usages_expr(e, var_usages, 2);
54                }
55            },
56
57            RynaExpr::NaryOperation(_, _, _, c, exprs) => {
58                RynaContext::count_usages_expr(c, var_usages, offset);
59
60                for e in exprs {
61                    RynaContext::count_usages_expr(e, var_usages, offset);
62                }
63            },
64
65            RynaExpr::AttributeAssignment(_, a, b, _) |
66            RynaExpr::BinaryOperation(_, _, _, a, b) => {
67                RynaContext::count_usages_expr(a, var_usages, offset);
68                RynaContext::count_usages_expr(b, var_usages, offset);
69            },
70
71            RynaExpr::If(_, ic, ib, ei, eb) => {
72                RynaContext::count_usages_expr(ic, var_usages, offset);
73                
74                for e in ib {
75                    RynaContext::count_usages_expr(e, var_usages, offset);
76                }
77
78                for (ei_h, ei_b) in ei {
79                    RynaContext::count_usages_expr(ei_h, var_usages, offset);
80                    
81                    for e in ei_b {
82                        RynaContext::count_usages_expr(e, var_usages, offset);
83                    }
84                }
85
86                if let Some(inner) = eb {
87                    for e in inner {
88                        RynaContext::count_usages_expr(e, var_usages, offset);
89                    }
90                }
91            },
92            
93            RynaExpr::Break(_) |
94            RynaExpr::Continue(_) |
95            RynaExpr::Literal(_, _) |
96            RynaExpr::Macro(_, _, _, _, _, _) |
97            RynaExpr::FunctionDefinition(_, _, _, _, _, _, _) |
98            RynaExpr::PrefixOperatorDefinition(_, _, _) |
99            RynaExpr::PostfixOperatorDefinition(_, _, _) |
100            RynaExpr::BinaryOperatorDefinition(_, _, _, _) |
101            RynaExpr::NaryOperatorDefinition(_, _, _, _) |
102            RynaExpr::ClassDefinition(_, _, _, _, _, _, _) |
103            RynaExpr::InterfaceDefinition(_, _, _, _, _, _, _, _) |
104            RynaExpr::InterfaceImplementation(_, _, _, _, _) |
105            RynaExpr::PrefixOperationDefinition(_, _, _, _, _, _, _, _) |
106            RynaExpr::PostfixOperationDefinition(_, _, _, _, _, _, _, _) |
107            RynaExpr::BinaryOperationDefinition(_, _, _, _, _, _, _, _) |
108            RynaExpr::NaryOperationDefinition(_, _, _, _, _, _, _, _) => { },
109
110            e => unreachable!("{:?}", e)
111        }
112    }
113
114    pub fn insert_moves_expr(&self, expr: &mut RynaExpr, var_usages: &mut FxHashMap<usize, usize>) {
115        match expr {
116            RynaExpr::Return(_, e) |
117            RynaExpr::AttributeAccess(_, e, _) |
118            RynaExpr::CompiledVariableDefinition(_, _, _, _, e, _) |
119            RynaExpr::CompiledVariableAssignment(_, _, _, _, e, _) => self.insert_moves_expr(e, var_usages),
120
121            RynaExpr::CompiledLambda(_, _, c, _, _, exprs) => {
122                let mut var_usages_lambda = FxHashMap::default();
123
124                for (_, e) in c {
125                    RynaContext::count_usages_expr(e, &mut var_usages_lambda, 2); // Set offset of 2 in order not to insert moves inside captures
126                }
127
128                for e in exprs {
129                    self.insert_moves_expr(e, &mut var_usages_lambda);
130                }                
131            }
132
133            RynaExpr::DoBlock(_, exprs, _) |
134            RynaExpr::Tuple(_, exprs) => {
135                for e in exprs {
136                    self.insert_moves_expr(e, var_usages);
137                }
138            },
139
140            RynaExpr::FunctionCall(_, id, _, exprs) => {
141                let move_id = self.get_function_id("move".into()).unwrap();
142                let deref_id = self.get_function_id("deref".into()).unwrap();
143
144                for e in exprs.iter_mut() {
145                    self.insert_moves_expr(e, var_usages);
146                }
147
148                if *id == deref_id && exprs.len() == 1 {
149                    if let RynaExpr::Variable(_, var_id, _, var_type, _) = &exprs[0] {
150                        if *var_usages.entry(*var_id).or_default() == 1 && !var_type.is_ref() {
151                            *id = move_id;
152
153                            // Sanity check and overload registration
154                            self.static_check(expr).unwrap();
155                        }
156                    }
157                }
158            },
159
160            RynaExpr::UnaryOperation(l, id, tm, e) => {
161                self.insert_moves_expr(e, var_usages);
162                
163                let move_id = self.get_function_id("move".into()).unwrap();
164
165                if *id == DEREF_UNOP_ID {
166                    if let RynaExpr::Variable(_, var_id, _, var_type, _) = &**e {
167                        if *var_usages.entry(*var_id).or_default() == 1 && !var_type.is_ref() {
168                            *expr = RynaExpr::FunctionCall(l.clone(), move_id, tm.clone(), vec!((**e).clone()));
169
170                            // Sanity check and overload registration
171                            self.static_check(expr).unwrap();
172                        }
173                    }
174                }
175            }
176
177            RynaExpr::NaryOperation(_, _, _, c, exprs) |
178            RynaExpr::CompiledFor(_, _, _, _, c, exprs) |
179            RynaExpr::While(_, c, exprs) => {
180                self.insert_moves_expr(c, var_usages);
181
182                for e in exprs {
183                    self.insert_moves_expr(e, var_usages);
184                }
185            },
186
187            RynaExpr::AttributeAssignment(_, a, b, _) |
188            RynaExpr::BinaryOperation(_, _, _, a, b) => {
189                self.insert_moves_expr(a, var_usages);
190                self.insert_moves_expr(b, var_usages);
191            },
192
193            RynaExpr::If(_, ic, ib, ei, eb) => {
194                self.insert_moves_expr(ic, var_usages);
195                
196                for e in ib {
197                    self.insert_moves_expr(e, var_usages);
198                }
199
200                for (ei_h, ei_b) in ei {
201                    self.insert_moves_expr(ei_h, var_usages);
202                    
203                    for e in ei_b {
204                        self.insert_moves_expr(e, var_usages);
205                    }
206                }
207
208                if let Some(inner) = eb {
209                    for e in inner {
210                        self.insert_moves_expr(e, var_usages);
211                    }
212                }
213            },
214            
215            RynaExpr::Break(_) |
216            RynaExpr::Continue(_) |
217            RynaExpr::Variable(_, _, _, _, _) |
218            RynaExpr::Literal(_, _) |
219            RynaExpr::Macro(_, _, _, _, _, _) |
220            RynaExpr::FunctionDefinition(_, _, _, _, _, _, _) |
221            RynaExpr::PrefixOperatorDefinition(_, _, _) |
222            RynaExpr::PostfixOperatorDefinition(_, _, _) |
223            RynaExpr::BinaryOperatorDefinition(_, _, _, _) |
224            RynaExpr::NaryOperatorDefinition(_, _, _, _) |
225            RynaExpr::ClassDefinition(_, _, _, _, _, _, _) |
226            RynaExpr::InterfaceDefinition(_, _, _, _, _, _, _, _) |
227            RynaExpr::InterfaceImplementation(_, _, _, _, _) |
228            RynaExpr::PrefixOperationDefinition(_, _, _, _, _, _, _, _) |
229            RynaExpr::PostfixOperationDefinition(_, _, _, _, _, _, _, _) |
230            RynaExpr::BinaryOperationDefinition(_, _, _, _, _, _, _, _) |
231            RynaExpr::NaryOperationDefinition(_, _, _, _, _, _, _, _) => { },
232
233            e => unreachable!("{:?}", e)
234        }
235    }
236
237    pub fn insert_moves(&self, body: &mut Vec<RynaExpr>) {
238        let mut var_usages = FxHashMap::default();
239
240        // Count usages
241        for i in body.iter() {
242            RynaContext::count_usages_expr(i, &mut var_usages, 1);
243        }
244        
245        // insert moves
246        for i in body {
247            self.insert_moves_expr(i, &mut var_usages);
248        }
249    }
250
251    pub fn strength_reduction_expr(&self, expr: &mut RynaExpr) {
252        match expr {
253            RynaExpr::UnaryOperation(_, _, _, e) |
254            RynaExpr::Return(_, e) |
255            RynaExpr::AttributeAccess(_, e, _) |
256            RynaExpr::CompiledVariableDefinition(_, _, _, _, e, _) |
257            RynaExpr::CompiledVariableAssignment(_, _, _, _, e, _) => self.strength_reduction_expr(e),
258
259            RynaExpr::AttributeAssignment(_, a, b, _) => {
260                self.strength_reduction_expr(a);
261                self.strength_reduction_expr(b);
262            }
263
264            RynaExpr::DoBlock(_, exprs, _) |
265            RynaExpr::CompiledLambda(_, _, _, _, _, exprs) |
266            RynaExpr::Tuple(_, exprs) => {
267                for e in exprs {
268                    self.strength_reduction_expr(e);
269                }
270            },
271
272            RynaExpr::FunctionCall(_, id, t, exprs) => {
273                for e in exprs.iter_mut() {
274                    self.strength_reduction_expr(e);
275                }
276
277                // Compile as
278                let as_id = self.get_function_id("as".into()).unwrap();
279
280                if *id == as_id && exprs.len() == 1 && t.len() == 1 {
281                    let expected_type = &t[0];
282                    let given_type = self.infer_type(&exprs[0]).unwrap();
283
284                    // Assume that the function will succeed
285                    if given_type == *expected_type {
286                        *expr = exprs[0].clone();
287                        return;
288                    }
289                }
290
291                // Compile fwd
292                let fwd_id = self.get_function_id("fwd".into()).unwrap();
293                let cfwd_id = self.get_function_id("cfwd".into()).unwrap();
294
295                if (*id == fwd_id || *id == cfwd_id) && exprs.len() == 1 && t.len() == 1 {
296                    let move_id = self.get_function_id("move".into()).unwrap();
297                    let deref_id = self.get_function_id("deref".into()).unwrap();
298                    let demut_id = self.get_function_id("demut".into()).unwrap();
299                    let ref_id = self.get_function_id("ref".into()).unwrap();
300                    let mut_id = self.get_function_id("mut".into()).unwrap();
301    
302                    let expected_type = &t[0];
303                    let given_type = self.infer_type(&exprs[0]).unwrap();
304
305                    // Identity
306                    if given_type == *expected_type {
307                        *expr = exprs[0].clone();
308                        return;
309                    }
310
311                    // Move / Deref
312                    if given_type == expected_type.clone().to_mut() {
313                        *id = if *id == fwd_id { move_id } else { deref_id };
314
315                        // Sanity check and overload registration
316                        self.static_check(expr).unwrap();
317
318                        return;
319                    }
320
321                    // Deref
322                    if given_type == expected_type.clone().to_ref() {
323                        *id = deref_id;
324
325                        // Sanity check and overload registration
326                        self.static_check(expr).unwrap();
327                        
328                        return;
329                    }
330
331                    // Ref
332                    if given_type.clone().to_ref() == *expected_type {
333                        if let Type::Ref(inner) = expected_type {
334                            t[0] = *inner.clone();
335                            *id = ref_id;
336
337                            // Sanity check and overload registration
338                            self.static_check(expr).unwrap();
339                            
340                            return;                            
341                        }
342                    }
343
344                    // Mut
345                    if given_type.clone().to_mut() == *expected_type {
346                        if let Type::MutRef(inner) = expected_type {
347                            t[0] = *inner.clone();
348                            *id = mut_id;
349
350                            // Sanity check and overload registration
351                            self.static_check(expr).unwrap();
352                            
353                            return;                            
354                        }
355                    }
356
357                    // Demut
358                    if let Type::MutRef(inner_1) = &given_type {
359                        if let Type::Ref(inner_2) = expected_type {
360                            if inner_1 == inner_2 {
361                                t[0] = *inner_2.clone();
362                                *id = demut_id;
363
364                                // Sanity check and overload registration
365                                self.static_check(expr).unwrap();
366                            }
367                        }
368                    }
369                }
370            }
371
372            RynaExpr::NaryOperation(_, _, _, c, exprs) |
373            RynaExpr::CompiledFor(_, _, _, _, c, exprs) |
374            RynaExpr::While(_, c, exprs) => {
375                self.strength_reduction_expr(c);
376
377                for e in exprs {
378                    self.strength_reduction_expr(e);
379                }
380            },
381
382            RynaExpr::BinaryOperation(l, id, _, a, b) => {
383                self.strength_reduction_expr(a);
384                self.strength_reduction_expr(b);
385
386                let t_a = self.infer_type(a).unwrap();
387                let t_b = self.infer_type(b).unwrap();
388
389                // Introduce increments and decrements
390                if *id == ASSIGN_BINOP_ID && t_a == INT.to_mut() && t_b == INT {
391                    if let RynaExpr::BinaryOperation(_, ADD_BINOP_ID, _, a_inner, b_inner) = &**b {
392                        if a_inner == a {
393                            if let RynaExpr::Literal(_, obj) = &**b_inner {
394                                if obj.get_type() == INT && *obj.get::<Integer>() == *ONE {
395                                    *expr = RynaExpr::FunctionCall(
396                                        l.clone(), 
397                                        self.get_function_id("inc".into()).unwrap(), 
398                                        vec!(), 
399                                        vec!(*a.clone())
400                                    );
401
402                                    // Sanity check and overload registration
403                                    self.static_check(expr).unwrap();
404
405                                    return;
406                                }
407                            }
408                        }
409                    }
410
411                    if let RynaExpr::BinaryOperation(_, SUB_BINOP_ID, _, a_inner, b_inner) = &**b {
412                        if a_inner == a {
413                            if let RynaExpr::Literal(_, obj) = &**b_inner {
414                                if obj.get_type() == INT && *obj.get::<Integer>() == *ONE {
415                                    *expr = RynaExpr::FunctionCall(
416                                        l.clone(), 
417                                        self.get_function_id("dec".into()).unwrap(), 
418                                        vec!(), 
419                                        vec!(*a.clone())
420                                    );
421
422                                    // Sanity check and overload registration
423                                    self.static_check(expr).unwrap();
424
425                                    return;
426                                }
427                            }
428                        }
429                    }
430                }
431
432                // Change multiplications for shifts when applicable
433                if *id == MUL_BINOP_ID && *t_a.deref_type() == INT && *t_b.deref_type() == INT {
434                    if let RynaExpr::Literal(_, obj) = &**a {
435                        if obj.get_type() == INT {
436                            let n = obj.get::<Integer>().clone();
437
438                            if is_valid_index(&n) && to_usize(&n).is_power_of_two() {
439                                let shift = u64::BITS - to_usize(&n).leading_zeros();
440    
441                                *expr = RynaExpr::BinaryOperation(
442                                    l.clone(),
443                                    SHL_BINOP_ID, 
444                                    vec!(), 
445                                    b.clone(), 
446                                    Box::new(RynaExpr::Literal(l.clone(), Object::new(Integer::from(shift - 1))))
447                                );
448    
449                                // Sanity check and overload registration
450                                self.static_check(expr).unwrap();
451    
452                                return;
453                            }
454                        }
455                    }
456
457                    if let RynaExpr::Literal(_, obj) = &**b {
458                        if obj.get_type() == INT {
459                            let n = obj.get::<Integer>().clone();
460
461                            if is_valid_index(&n) && to_usize(&n).is_power_of_two() {
462                                let shift = u64::BITS - to_usize(&n).leading_zeros();
463    
464                                *expr = RynaExpr::BinaryOperation(
465                                    l.clone(),
466                                    SHL_BINOP_ID, 
467                                    vec!(), 
468                                    a.clone(), 
469                                    Box::new(RynaExpr::Literal(l.clone(), Object::new(Integer::from(shift - 1))))
470                                );
471    
472                                // Sanity check and overload registration
473                                self.static_check(expr).unwrap();
474                            }
475                        }
476                    }
477                }
478            },
479
480            RynaExpr::If(_, ic, ib, ei, eb) => {
481                self.strength_reduction_expr(ic);
482                
483                for e in ib {
484                    self.strength_reduction_expr(e);
485                }
486
487                for (ei_h, ei_b) in ei {
488                    self.strength_reduction_expr(ei_h);
489                    
490                    for e in ei_b {
491                        self.strength_reduction_expr(e);
492                    }
493                }
494
495                if let Some(inner) = eb {
496                    for e in inner {
497                        self.strength_reduction_expr(e);
498                    }
499                }
500            },
501            
502            RynaExpr::Break(_) |
503            RynaExpr::Continue(_) |
504            RynaExpr::Variable(_, _, _, _, _) |
505            RynaExpr::Literal(_, _) |
506            RynaExpr::Macro(_, _, _, _, _, _) |
507            RynaExpr::FunctionDefinition(_, _, _, _, _, _, _) |
508            RynaExpr::PrefixOperatorDefinition(_, _, _) |
509            RynaExpr::PostfixOperatorDefinition(_, _, _) |
510            RynaExpr::BinaryOperatorDefinition(_, _, _, _) |
511            RynaExpr::NaryOperatorDefinition(_, _, _, _) |
512            RynaExpr::ClassDefinition(_, _, _, _, _, _, _) |
513            RynaExpr::InterfaceDefinition(_, _, _, _, _, _, _, _) |
514            RynaExpr::InterfaceImplementation(_, _, _, _, _) |
515            RynaExpr::PrefixOperationDefinition(_, _, _, _, _, _, _, _) |
516            RynaExpr::PostfixOperationDefinition(_, _, _, _, _, _, _, _) |
517            RynaExpr::BinaryOperationDefinition(_, _, _, _, _, _, _, _) |
518            RynaExpr::NaryOperationDefinition(_, _, _, _, _, _, _, _) => { },
519
520            e => unreachable!("{:?}", e)
521        }
522    }
523
524    pub fn inlining_weight(&self, body: &Vec<RynaExpr>) -> f32 {
525        self.compiled_form_body_size(body, false).unwrap() as f32
526    }
527
528    pub fn max_variable(expr: &RynaExpr, offset: &mut usize) {
529        match expr {
530            RynaExpr::Variable(_, id, _, _, _) => {
531                *offset = (*offset).max(*id);
532            },
533
534            RynaExpr::CompiledVariableDefinition(_, id, _, _, e, _) |
535            RynaExpr::CompiledVariableAssignment(_, id, _, _, e, _) => {
536                *offset = (*offset).max(*id);
537                RynaContext::max_variable(e, offset)
538            },
539
540            RynaExpr::UnaryOperation(_, _, _, e) |
541            RynaExpr::AttributeAccess(_, e, _) |
542            RynaExpr::Return(_, e) => RynaContext::max_variable(e, offset),
543
544            RynaExpr::DoBlock(_, exprs, _) |
545            RynaExpr::CompiledLambda(_, _, _, _, _, exprs) |
546            RynaExpr::FunctionCall(_, _, _, exprs) |
547            RynaExpr::Tuple(_, exprs) => {
548                for e in exprs {
549                    RynaContext::max_variable(e, offset);
550                }
551            },
552
553            RynaExpr::CompiledFor(_, iterator_idx, element_idx, _, c, exprs) => {
554                *offset = (*offset).max(*iterator_idx);
555                *offset = (*offset).max(*element_idx);
556
557                RynaContext::max_variable(c, offset);
558
559                for e in exprs {
560                    RynaContext::max_variable(e, offset);
561                }
562            },
563
564            RynaExpr::While(_, c, exprs) => {
565                RynaContext::max_variable(c, offset);
566
567                for e in exprs {
568                    RynaContext::max_variable(e, offset);
569                }
570            },
571
572            RynaExpr::NaryOperation(_, _, _, c, exprs) => {
573                RynaContext::max_variable(c, offset);
574
575                for e in exprs {
576                    RynaContext::max_variable(e, offset);
577                }
578            },
579
580            RynaExpr::AttributeAssignment(_, a, b, _) |
581            RynaExpr::BinaryOperation(_, _, _, a, b) => {
582                RynaContext::max_variable(a, offset);
583                RynaContext::max_variable(b, offset);
584            },
585
586            RynaExpr::If(_, ic, ib, ei, eb) => {
587                RynaContext::max_variable(ic, offset);
588                
589                for e in ib {
590                    RynaContext::max_variable(e, offset);
591                }
592
593                for (ei_h, ei_b) in ei {
594                    RynaContext::max_variable(ei_h, offset);
595                    
596                    for e in ei_b {
597                        RynaContext::max_variable(e, offset);
598                    }
599                }
600
601                if let Some(inner) = eb {
602                    for e in inner {
603                        RynaContext::max_variable(e, offset);
604                    }
605                }
606            },
607            
608            RynaExpr::Break(_) |
609            RynaExpr::Continue(_) |
610            RynaExpr::Literal(_, _) |
611            RynaExpr::Macro(_, _, _, _, _, _) |
612            RynaExpr::FunctionDefinition(_, _, _, _, _, _, _) |
613            RynaExpr::PrefixOperatorDefinition(_, _, _) |
614            RynaExpr::PostfixOperatorDefinition(_, _, _) |
615            RynaExpr::BinaryOperatorDefinition(_, _, _, _) |
616            RynaExpr::NaryOperatorDefinition(_, _, _, _) |
617            RynaExpr::ClassDefinition(_, _, _, _, _, _, _) |
618            RynaExpr::InterfaceDefinition(_, _, _, _, _, _, _, _) |
619            RynaExpr::InterfaceImplementation(_, _, _, _, _) |
620            RynaExpr::PrefixOperationDefinition(_, _, _, _, _, _, _, _) |
621            RynaExpr::PostfixOperationDefinition(_, _, _, _, _, _, _, _) |
622            RynaExpr::BinaryOperationDefinition(_, _, _, _, _, _, _, _) |
623            RynaExpr::NaryOperationDefinition(_, _, _, _, _, _, _, _) => { },
624
625            e => unreachable!("{:?}", e)
626        }
627    }
628
629    pub fn offset_variables(expr: &mut RynaExpr, offset: usize) {
630        match expr {
631            RynaExpr::Variable(_, id, _, _, g) => {
632                if !*g {
633                    *id += offset;                    
634                }
635            },
636
637            RynaExpr::CompiledVariableDefinition(_, id, _, _, e, g) |
638            RynaExpr::CompiledVariableAssignment(_, id, _, _, e, g) => {
639                if !*g {
640                    *id += offset;
641                }
642
643                RynaContext::offset_variables(e, offset)
644            },
645
646            RynaExpr::UnaryOperation(_, _, _, e) |
647            RynaExpr::AttributeAccess(_, e, _) |
648            RynaExpr::Return(_, e) => RynaContext::offset_variables(e, offset),
649
650            RynaExpr::CompiledLambda(_, _, c, _, _, exprs) => {
651                for (_, e) in c {
652                    RynaContext::offset_variables(e, offset);
653                }
654
655                for e in exprs {
656                    RynaContext::offset_variables(e, offset);
657                }
658            }
659
660            RynaExpr::DoBlock(_, exprs, _) |
661            RynaExpr::FunctionCall(_, _, _, exprs) |
662            RynaExpr::Tuple(_, exprs) => {
663                for e in exprs {
664                    RynaContext::offset_variables(e, offset);
665                }
666            },
667
668            RynaExpr::CompiledFor(_, iterator_idx, element_idx, _, c, exprs) => {
669                *iterator_idx += offset;
670                *element_idx += offset;
671
672                RynaContext::offset_variables(c, offset);
673                
674                for e in exprs {
675                    RynaContext::offset_variables(e, offset);
676                }
677            }
678
679            RynaExpr::While(_, c, exprs) => {
680                RynaContext::offset_variables(c, offset);
681
682                for e in exprs {
683                    RynaContext::offset_variables(e, offset);
684                }
685            },
686
687            RynaExpr::NaryOperation(_, _, _, c, exprs) => {
688                RynaContext::offset_variables(c, offset);
689
690                for e in exprs {
691                    RynaContext::offset_variables(e, offset);
692                }
693            },
694
695            RynaExpr::AttributeAssignment(_, a, b, _) |
696            RynaExpr::BinaryOperation(_, _, _, a, b) => {
697                RynaContext::offset_variables(a, offset);
698                RynaContext::offset_variables(b, offset);
699            },
700
701            RynaExpr::If(_, ic, ib, ei, eb) => {
702                RynaContext::offset_variables(ic, offset);
703                
704                for e in ib {
705                    RynaContext::offset_variables(e, offset);
706                }
707
708                for (ei_h, ei_b) in ei {
709                    RynaContext::offset_variables(ei_h, offset);
710                    
711                    for e in ei_b {
712                        RynaContext::offset_variables(e, offset);
713                    }
714                }
715
716                if let Some(inner) = eb {
717                    for e in inner {
718                        RynaContext::offset_variables(e, offset);
719                    }
720                }
721            },
722            
723            RynaExpr::Break(_) |
724            RynaExpr::Continue(_) |
725            RynaExpr::Literal(_, _) |
726            RynaExpr::Macro(_, _, _, _, _, _) |
727            RynaExpr::FunctionDefinition(_, _, _, _, _, _, _) |
728            RynaExpr::PrefixOperatorDefinition(_, _, _) |
729            RynaExpr::PostfixOperatorDefinition(_, _, _) |
730            RynaExpr::BinaryOperatorDefinition(_, _, _, _) |
731            RynaExpr::NaryOperatorDefinition(_, _, _, _) |
732            RynaExpr::ClassDefinition(_, _, _, _, _, _, _) |
733            RynaExpr::InterfaceDefinition(_, _, _, _, _, _, _, _) |
734            RynaExpr::InterfaceImplementation(_, _, _, _, _) |
735            RynaExpr::PrefixOperationDefinition(_, _, _, _, _, _, _, _) |
736            RynaExpr::PostfixOperationDefinition(_, _, _, _, _, _, _, _) |
737            RynaExpr::BinaryOperationDefinition(_, _, _, _, _, _, _, _) |
738            RynaExpr::NaryOperationDefinition(_, _, _, _, _, _, _, _) => { },
739
740            e => unreachable!("{:?}", e)
741        }
742    }
743
744    pub fn inline_body(&self, mut body: Vec<RynaExpr>, args: Vec<RynaExpr>, var_offset: &mut usize, l: &Location) -> Vec<RynaExpr> {
745        let mut res = vec!();
746
747        // Get number of vars
748        let arg_num = args.len();
749        let mut func_offset = 0;
750
751        for line in body.iter() {
752            RynaContext::max_variable(line, &mut func_offset);
753        }
754
755        // Define variables
756        for (idx, arg) in args.into_iter().enumerate() {
757            res.push(RynaExpr::CompiledVariableDefinition(
758                l.clone(),
759                idx + *var_offset + 1,
760                format!("__arg_{}__", idx + *var_offset + 1),
761                self.infer_type(&arg).unwrap(),
762                Box::new(arg),
763                false
764            ))
765        }
766
767        // Map body
768        for line in body.iter_mut() {
769            RynaContext::offset_variables(line, *var_offset + 1);
770        }
771
772        res.append(&mut body);
773
774        // Update variable number
775        *var_offset += func_offset + arg_num + 1;
776
777        res
778    }
779
780    pub fn inline_functions_expr(&self, expr: &mut RynaExpr, offset: &mut usize) {
781        match expr {
782            RynaExpr::Return(_, e) |
783            RynaExpr::AttributeAccess(_, e, _) |
784            RynaExpr::CompiledVariableDefinition(_, _, _, _, e, _) |
785            RynaExpr::CompiledVariableAssignment(_, _, _, _, e, _) => self.inline_functions_expr(e, offset),
786
787            RynaExpr::AttributeAssignment(_, a, b, _) => {
788                self.inline_functions_expr(a, offset);
789                self.inline_functions_expr(b, offset);
790            }
791
792            RynaExpr::DoBlock(_, exprs, _) |
793            RynaExpr::CompiledLambda(_, _, _, _, _, exprs) |
794            RynaExpr::Tuple(_, exprs) => {
795                self.inline_functions(exprs, offset);
796            },
797
798            RynaExpr::UnaryOperation(l, id, t, e) => {
799                self.inline_functions_expr(e, offset);
800
801                let arg_types = self.infer_type(e).unwrap();
802                let templates = Type::And(t.clone());
803
804                let cache_entry = self.cache.templates.unary.inner_borrow_mut();
805
806                let body = cache_entry.iter().find(|i| {
807                    let other_tm = Type::And(i.0.1.clone());
808
809                    i.0.0 == *id && templates.bindable_to(&other_tm, self) && arg_types.bindable_to(&i.0.2[0], self)
810                }).map(|i| i.1);
811
812                if let Some(inner) = body {
813                    let weight = self.inlining_weight(inner);
814
815                    if weight < INLINE_THRESHOLD {
816                        let mut inlined_body = self.inline_body(inner.clone(), vec!(*e.clone()), offset, l);
817                        let return_type = self.infer_type(expr).unwrap();
818
819                        // Add empty return if needed
820                        if let Type::Empty = return_type {
821                            if RynaContext::ensured_return_check_body(&inlined_body, &Location::none(), "Operation").is_err() {
822                                inlined_body.push(RynaExpr::Return(Location::none(), Box::new(RynaExpr::Literal(Location::none(), Object::empty()))));
823                            }
824                        }
825
826                        *expr = RynaExpr::DoBlock(Location::none(), inlined_body, return_type);
827
828                        // Sanity check
829                        self.static_check(expr).unwrap();
830                    }
831                }
832            }
833
834            RynaExpr::BinaryOperation(l, id, t, a, b) => {
835                self.inline_functions_expr(a, offset);
836                self.inline_functions_expr(b, offset);
837
838                let arg_types = Type::And(vec!(self.infer_type(a).unwrap(), self.infer_type(b).unwrap()));
839                let templates = Type::And(t.clone());
840
841                let cache_entry = self.cache.templates.binary.inner_borrow_mut();
842
843                let body = cache_entry.iter().find(|i| {
844                    let other_tm = Type::And(i.0.1.clone());
845                    let other_args = Type::And(i.0.2.clone());
846
847                    i.0.0 == *id && templates.bindable_to(&other_tm, self) && arg_types.bindable_to(&other_args, self)
848                }).map(|i| i.1);
849
850                if let Some(inner) = body {
851                    let weight = self.inlining_weight(inner);
852
853                    if weight < INLINE_THRESHOLD {
854                        let mut inlined_body = self.inline_body(inner.clone(), vec!(*a.clone(), *b.clone()), offset, l);
855                        let return_type = self.infer_type(expr).unwrap();
856
857                        // Add empty return if needed
858                        if let Type::Empty = return_type {
859                            if RynaContext::ensured_return_check_body(&inlined_body, &Location::none(), "Operation").is_err() {
860                                inlined_body.push(RynaExpr::Return(Location::none(), Box::new(RynaExpr::Literal(Location::none(), Object::empty()))));
861                            }
862                        }
863
864                        *expr = RynaExpr::DoBlock(Location::none(), inlined_body, return_type);
865
866                        // Sanity check
867                        self.static_check(expr).unwrap();
868                    }
869                }
870            }
871
872            RynaExpr::NaryOperation(l, id, t, c, exprs) => {
873                self.inline_functions_expr(c, offset);
874                self.inline_functions(exprs, offset);
875
876                let mut arg_types_vec = vec!(self.infer_type(c).unwrap());
877                arg_types_vec.extend(exprs.iter().map(|i| self.infer_type(i).unwrap()));
878                let arg_types = Type::And(arg_types_vec);
879                let templates = Type::And(t.clone());
880
881                let cache_entry = self.cache.templates.nary.inner_borrow_mut();
882
883                let body = cache_entry.iter().find(|i| {
884                    let other_tm = Type::And(i.0.1.clone());
885                    let other_args = Type::And(i.0.2.clone());
886
887                    i.0.0 == *id && templates.bindable_to(&other_tm, self) && arg_types.bindable_to(&other_args, self)
888                }).map(|i| i.1);
889
890                if let Some(inner) = body {
891                    let weight = self.inlining_weight(inner);
892
893                    if weight < INLINE_THRESHOLD {
894                        let mut args_vec = vec!(*c.clone());
895                        args_vec.extend(exprs.iter().cloned());
896        
897                        let mut inlined_body = self.inline_body(inner.clone(), args_vec, offset, l);
898                        let return_type = self.infer_type(expr).unwrap();
899
900                        // Add empty return if needed
901                        if let Type::Empty = return_type {
902                            if RynaContext::ensured_return_check_body(&inlined_body, &Location::none(), "Operation").is_err() {
903                                inlined_body.push(RynaExpr::Return(Location::none(), Box::new(RynaExpr::Literal(Location::none(), Object::empty()))));
904                            }
905                        }
906
907                        *expr = RynaExpr::DoBlock(Location::none(), inlined_body, return_type);
908
909                        // Sanity check
910                        self.static_check(expr).unwrap();
911                    }
912                }
913            }
914
915            RynaExpr::FunctionCall(l, id, t, args) => {
916                self.inline_functions(args, offset);
917                
918                // Do not inline destructor calls
919                if self.is_dtor_id(*id) {
920                    return;
921                }
922
923                let arg_types = Type::And(args.iter().map(|i| self.infer_type(i).unwrap()).collect());
924                let templates = Type::And(t.clone());
925
926                let cache_entry = self.cache.templates.functions.inner_borrow_mut();
927
928                let body = cache_entry.iter().find(|i| {
929                    let other_tm = Type::And(i.0.1.clone());
930                    let other_args = Type::And(i.0.2.clone());
931
932                    i.0.0 == *id && templates.bindable_to(&other_tm, self) && arg_types.bindable_to(&other_args, self)
933                }).map(|i| i.1);
934
935                if let Some(inner) = body {
936                    let weight = self.inlining_weight(inner);
937
938                    if weight < INLINE_THRESHOLD {
939                        let mut inlined_body = self.inline_body(inner.clone(), args.clone(), offset, l);
940                        let return_type = self.infer_type(expr).unwrap();
941
942                        // Add empty return if needed
943                        if let Type::Empty = return_type {
944                            if RynaContext::ensured_return_check_body(&inlined_body, &Location::none(), "Operation").is_err() {
945                                inlined_body.push(RynaExpr::Return(Location::none(), Box::new(RynaExpr::Literal(Location::none(), Object::empty()))));
946                            }
947                        }
948
949                        *expr = RynaExpr::DoBlock(Location::none(), inlined_body, return_type);
950
951                        // Sanity check
952                        self.static_check(expr).unwrap();
953                    }
954                }
955            }
956
957            RynaExpr::CompiledFor(_, _, _, _, c, exprs) |
958            RynaExpr::While(_, c, exprs) => {
959                self.inline_functions_expr(c, offset);
960                self.inline_functions(exprs, offset);
961            },
962
963            RynaExpr::If(_, ic, ib, ei, eb) => {
964                self.inline_functions_expr(ic, offset);
965                self.inline_functions(ib, offset);
966
967                for (ei_h, ei_b) in ei {
968                    self.inline_functions_expr(ei_h, offset);
969                    self.inline_functions(ei_b, offset);
970                }
971
972                if let Some(inner) = eb {
973                    self.inline_functions(inner, offset);
974                }
975            },
976            
977            RynaExpr::Break(_) |
978            RynaExpr::Continue(_) |
979            RynaExpr::Variable(_, _, _, _, _) |
980            RynaExpr::Literal(_, _) |
981            RynaExpr::Macro(_, _, _, _, _, _) |
982            RynaExpr::FunctionDefinition(_, _, _, _, _, _, _) |
983            RynaExpr::PrefixOperatorDefinition(_, _, _) |
984            RynaExpr::PostfixOperatorDefinition(_, _, _) |
985            RynaExpr::BinaryOperatorDefinition(_, _, _, _) |
986            RynaExpr::NaryOperatorDefinition(_, _, _, _) |
987            RynaExpr::ClassDefinition(_, _, _, _, _, _, _) |
988            RynaExpr::InterfaceDefinition(_, _, _, _, _, _, _, _) |
989            RynaExpr::InterfaceImplementation(_, _, _, _, _) |
990            RynaExpr::PrefixOperationDefinition(_, _, _, _, _, _, _, _) |
991            RynaExpr::PostfixOperationDefinition(_, _, _, _, _, _, _, _) |
992            RynaExpr::BinaryOperationDefinition(_, _, _, _, _, _, _, _) |
993            RynaExpr::NaryOperationDefinition(_, _, _, _, _, _, _, _) => { },
994
995            e => unreachable!("{:?}", e)
996        }
997    }
998
999    pub fn inline_functions(&self, body: &mut Vec<RynaExpr>, offset: &mut usize) {
1000        for i in body {
1001            self.inline_functions_expr(i, offset);
1002        } 
1003    }
1004
1005    pub fn strength_reduction(&self, body: &mut Vec<RynaExpr>) {
1006        for i in body {
1007            self.strength_reduction_expr(i);
1008        } 
1009    }
1010
1011    pub fn optimize(&self, body: &mut Vec<RynaExpr>) {
1012        self.insert_moves(body);
1013        self.strength_reduction(body);
1014    } 
1015
1016    pub fn is_constant_expr(&self, expr: &RynaExpr, consts: &FxHashMap<usize, bool>) -> bool {
1017        macro_rules! is_num {
1018            ($expr: expr) => {
1019                match *self.infer_type($expr).unwrap().deref_type().deref_type() {
1020                    Type::Basic(crate::types::INT_ID) | Type::Basic(crate::types::FLOAT_ID) => true,
1021                    _ => false
1022                }
1023            };
1024        }
1025
1026        match expr {
1027            RynaExpr::Literal(..) => true,
1028            RynaExpr::Variable(_, id, _, _, g) => !g && *consts.get(id).unwrap_or(&false), // Assume globals are not constant
1029
1030            RynaExpr::UnaryOperation(_, id, _, e) => {
1031                CONST_UNOP_IDS.contains(id) && self.is_constant_expr(e, consts) && is_num!(e)
1032            },
1033            RynaExpr::BinaryOperation(_, id, _, a, b) => {
1034                CONST_BINOP_IDS.contains(id) && self.is_constant_expr(a, consts) && self.is_constant_expr(b, consts) && is_num!(a) && is_num!(b)
1035            },
1036
1037            RynaExpr::NaryOperation(_, id, _, c, exprs) => {
1038                CONST_NARYOP_IDS.contains(id) && self.is_constant_expr(c, consts) &&
1039                exprs.iter().all(|i| self.is_constant_expr(i, consts))
1040            },
1041
1042            RynaExpr::FunctionCall(_, id, _, exprs) => {
1043                CONST_FUNC_IDS.contains(id) && exprs.iter().all(|i| self.is_constant_expr(i, consts))
1044            }
1045            
1046            _ => false
1047        }
1048    }
1049
1050    pub fn compute_constant_expr(expr: &RynaExpr, const_exprs: &FxHashMap<usize, RynaExpr>) -> Object {
1051        match expr {
1052            RynaExpr::Literal(_, obj) => obj.clone(),
1053            RynaExpr::Variable(_, id, _, _, _) => RynaContext::compute_constant_expr(const_exprs.get(id).unwrap(), const_exprs),
1054
1055            RynaExpr::UnaryOperation(_, id, _, e) => {
1056                let inner = RynaContext::compute_constant_expr(e, const_exprs);
1057                let t = inner.get_type();
1058
1059                match *id {
1060                    NEG_UNOP_ID if t == INT => Object::new(-inner.get::<Integer>().clone()),
1061                    NEG_UNOP_ID if t == FLOAT => Object::new(-*inner.get::<f64>()),
1062                    _ => unreachable!()
1063                }    
1064            },
1065
1066            RynaExpr::BinaryOperation(_, id, _, a, b) => {
1067                let a_inner = RynaContext::compute_constant_expr(a, const_exprs);
1068                let b_inner = RynaContext::compute_constant_expr(b, const_exprs);
1069                let ta = a_inner.get_type();
1070                let tb = b_inner.get_type();
1071
1072                macro_rules! bin_op {
1073                    ($op: tt, $type_a: ident, $type_b: ident) => {
1074                        Object::new(a_inner.get::<$type_a>().clone() $op b_inner.get::<$type_b>().clone())
1075                    };
1076                }
1077
1078                macro_rules! bin_op_l {
1079                    ($op: tt, $type_a: ident, $type_b: ident, $func: ident) => {
1080                        {
1081                            use crate::integer_ext::*;
1082                            Object::new($func(&*a_inner.get::<$type_a>()) $op b_inner.get::<$type_b>().clone())    
1083                        }
1084                    };
1085                }
1086
1087                macro_rules! bin_op_r {
1088                    ($op: tt, $type_a: ident, $type_b: ident, $func: ident) => {
1089                        {
1090                            use crate::integer_ext::*;
1091                            Object::new(a_inner.get::<$type_a>().clone() $op $func(&*b_inner.get::<$type_b>()))    
1092                        }
1093                    };
1094                }
1095
1096                match *id {
1097                    ADD_BINOP_ID if ta == INT && tb == INT => bin_op!(+, Integer, Integer),
1098                    ADD_BINOP_ID if ta == FLOAT && tb == FLOAT => bin_op!(+, f64, f64),
1099                    ADD_BINOP_ID if ta == INT && tb == FLOAT => bin_op_l!(+, Integer, f64, to_f64),
1100                    ADD_BINOP_ID if ta == FLOAT && tb == INT => bin_op_r!(+, f64, Integer, to_f64),
1101                    
1102                    SUB_BINOP_ID if ta == INT && tb == INT => bin_op!(-, Integer, Integer),
1103                    SUB_BINOP_ID if ta == FLOAT && tb == FLOAT => bin_op!(-, f64, f64),
1104                    SUB_BINOP_ID if ta == INT && tb == FLOAT => bin_op_l!(-, Integer, f64, to_f64),
1105                    SUB_BINOP_ID if ta == FLOAT && tb == INT => bin_op_r!(-, f64, Integer, to_f64),
1106                    
1107                    MUL_BINOP_ID if ta == INT && tb == INT => bin_op!(*, Integer, Integer),
1108                    MUL_BINOP_ID if ta == FLOAT && tb == FLOAT => bin_op!(*, f64, f64),
1109                    MUL_BINOP_ID if ta == INT && tb == FLOAT => bin_op_l!(*, Integer, f64, to_f64),
1110                    MUL_BINOP_ID if ta == FLOAT && tb == INT => bin_op_r!(*, f64, Integer, to_f64),
1111                    
1112                    DIV_BINOP_ID if ta == INT && tb == INT => bin_op!(/, Integer, Integer),
1113                    DIV_BINOP_ID if ta == FLOAT && tb == FLOAT => bin_op!(/, f64, f64),
1114                    DIV_BINOP_ID if ta == INT && tb == FLOAT => bin_op_l!(/, Integer, f64, to_f64),
1115                    DIV_BINOP_ID if ta == FLOAT && tb == INT => bin_op_r!(/, f64, Integer, to_f64),
1116                    
1117                    MOD_BINOP_ID if ta == INT && tb == INT => bin_op!(%, Integer, Integer),
1118                    MOD_BINOP_ID if ta == FLOAT && tb == FLOAT => bin_op!(%, f64, f64),
1119                    MOD_BINOP_ID if ta == INT && tb == FLOAT => bin_op_l!(%, Integer, f64, to_f64),
1120                    MOD_BINOP_ID if ta == FLOAT && tb == INT => bin_op_r!(%, f64, Integer, to_f64),
1121
1122                    _ => unreachable!()
1123                }
1124            },
1125
1126            RynaExpr::NaryOperation(_, _, _, _, _) => todo!(),
1127            RynaExpr::FunctionCall(_, _, _, _) => todo!(),
1128            
1129            _ => unreachable!()
1130        }
1131    }
1132    
1133    pub fn get_constants(&self, expr: &RynaExpr, consts: &mut FxHashMap<usize, bool>, const_exprs: &mut FxHashMap<usize, RynaExpr>) {
1134        match expr {
1135            RynaExpr::UnaryOperation(_, _, _, e) |
1136            RynaExpr::AttributeAccess(_, e, _) |
1137            RynaExpr::Return(_, e)  => self.get_constants(e, consts, const_exprs),
1138            
1139            RynaExpr::CompiledVariableDefinition(_, id, _, _, e, g) => { 
1140                if !g && self.is_constant_expr(e, consts) { // Globals are not constant
1141                    consts.insert(*id, true);
1142                    const_exprs.insert(*id, RynaExpr::Literal(Location::none(), RynaContext::compute_constant_expr(e, const_exprs)));    
1143                }
1144            },
1145            RynaExpr::CompiledVariableAssignment(_, id, _, _, _, _) => { consts.insert(*id, false); },
1146
1147            RynaExpr::DoBlock(_, exprs, _) |
1148            RynaExpr::FunctionCall(_, _, _, exprs) |
1149            RynaExpr::Tuple(_, exprs) => {
1150                for e in exprs {
1151                    self.get_constants(e, consts, const_exprs);
1152                }
1153            },
1154
1155            RynaExpr::CompiledFor(_, _, _, _, c, exprs) |
1156            RynaExpr::While(_, c, exprs) => {
1157                self.get_constants(c, consts, const_exprs);
1158
1159                for e in exprs {
1160                    self.get_constants(e, consts, const_exprs);
1161                }
1162            },
1163
1164            RynaExpr::NaryOperation(_, _, _, c, exprs) => {
1165                self.get_constants(c, consts, const_exprs);
1166
1167                for e in exprs {
1168                    self.get_constants(e, consts, const_exprs);
1169                }
1170            },
1171
1172            RynaExpr::AttributeAssignment(_, a, b, _) |
1173            RynaExpr::BinaryOperation(_, _, _, a, b) => {
1174                self.get_constants(a, consts, const_exprs);
1175                self.get_constants(b, consts, const_exprs);
1176            },
1177
1178            RynaExpr::If(_, ic, ib, ei, eb) => {
1179                self.get_constants(ic, consts, const_exprs);
1180                
1181                for e in ib {
1182                    self.get_constants(e, consts, const_exprs);
1183                }
1184
1185                for (ei_h, ei_b) in ei {
1186                    self.get_constants(ei_h, consts, const_exprs);
1187                    
1188                    for e in ei_b {
1189                        self.get_constants(e, consts, const_exprs);
1190                    }
1191                }
1192
1193                if let Some(inner) = eb {
1194                    for e in inner {
1195                        self.get_constants(e, consts, const_exprs);
1196                    }
1197                }
1198            },
1199            
1200            RynaExpr::CompiledLambda(_, _, _, _, _, _) |
1201            RynaExpr::Variable(_, _, _, _, _) |
1202            RynaExpr::Break(_) |
1203            RynaExpr::Continue(_) |
1204            RynaExpr::Literal(_, _) |
1205            RynaExpr::Macro(_, _, _, _, _, _) |
1206            RynaExpr::FunctionDefinition(_, _, _, _, _, _, _) |
1207            RynaExpr::PrefixOperatorDefinition(_, _, _) |
1208            RynaExpr::PostfixOperatorDefinition(_, _, _) |
1209            RynaExpr::BinaryOperatorDefinition(_, _, _, _) |
1210            RynaExpr::NaryOperatorDefinition(_, _, _, _) |
1211            RynaExpr::ClassDefinition(_, _, _, _, _, _, _) |
1212            RynaExpr::InterfaceDefinition(_, _, _, _, _, _, _, _) |
1213            RynaExpr::InterfaceImplementation(_, _, _, _, _) |
1214            RynaExpr::PrefixOperationDefinition(_, _, _, _, _, _, _, _) |
1215            RynaExpr::PostfixOperationDefinition(_, _, _, _, _, _, _, _) |
1216            RynaExpr::BinaryOperationDefinition(_, _, _, _, _, _, _, _) |
1217            RynaExpr::NaryOperationDefinition(_, _, _, _, _, _, _, _) => { },
1218
1219            e => unreachable!("{:?}", e)
1220        }
1221    }
1222    
1223    fn sub_variables(&self, expr: &mut RynaExpr, assigned_exprs: &mut FxHashMap<usize, RynaExpr>) {
1224        match expr {
1225            RynaExpr::Variable(l, id, _, _, g) => {
1226                if !*g && assigned_exprs.contains_key(id) { // Do not subtitute globals
1227                    let mut_id = self.get_function_id("mut".into()).unwrap();
1228                    let const_expr = assigned_exprs[id].clone();
1229                    let t = self.infer_type(&const_expr).unwrap();
1230
1231                    *expr = RynaExpr::FunctionCall(l.clone(), mut_id, vec!(t), vec!(const_expr));
1232                    
1233                    // Sanity check and overload registration
1234                    self.static_check(expr).unwrap();
1235                }
1236            }
1237
1238            RynaExpr::CompiledVariableDefinition(_, _, _, _, e, _) |
1239            RynaExpr::CompiledVariableAssignment(_, _, _, _, e, _) |
1240            RynaExpr::AttributeAccess(_, e, _) |
1241            RynaExpr::Return(_, e)  => self.sub_variables(e, assigned_exprs),
1242
1243            RynaExpr::UnaryOperation(_, _, _, e) => {
1244                self.sub_variables(e, assigned_exprs);
1245
1246                // Static check and overload resolution
1247                self.static_check(&expr).unwrap();
1248            }
1249
1250            RynaExpr::DoBlock(_, exprs, _) |
1251            RynaExpr::Tuple(_, exprs) => {
1252                for e in exprs {
1253                    self.sub_variables(e, assigned_exprs);
1254                }
1255            },
1256
1257            RynaExpr::FunctionCall(_, _, _, exprs) => {
1258                for e in exprs {
1259                    self.sub_variables(e, assigned_exprs);
1260                }
1261
1262                // Static check and overload resolution
1263                self.static_check(&expr).unwrap();
1264            }
1265
1266            RynaExpr::CompiledFor(_, _, _, _, c, exprs) |
1267            RynaExpr::While(_, c, exprs) => {
1268                self.sub_variables(c, assigned_exprs);
1269
1270                for e in exprs {
1271                    self.sub_variables(e, assigned_exprs);
1272                }
1273            },
1274
1275            RynaExpr::NaryOperation(_, _, _, c, exprs) => {
1276                self.sub_variables(c, assigned_exprs);
1277
1278                for e in exprs {
1279                    self.sub_variables(e, assigned_exprs);
1280                }
1281
1282                // Static check and overload resolution
1283                self.static_check(&expr).unwrap();
1284            },
1285
1286            RynaExpr::AttributeAssignment(_, a, b, _) => {
1287                self.sub_variables(a, assigned_exprs);
1288                self.sub_variables(b, assigned_exprs);
1289            }
1290
1291            RynaExpr::BinaryOperation(_, _, _, a, b) => {
1292                self.sub_variables(a, assigned_exprs);
1293                self.sub_variables(b, assigned_exprs);
1294
1295                // Static check and overload resolution
1296                self.static_check(&expr).unwrap();
1297            },
1298
1299            RynaExpr::If(_, ic, ib, ei, eb) => {
1300                self.sub_variables(ic, assigned_exprs);
1301                
1302                for e in ib {
1303                    self.sub_variables(e, assigned_exprs);
1304                }
1305
1306                for (ei_h, ei_b) in ei {
1307                    self.sub_variables(ei_h, assigned_exprs);
1308                    
1309                    for e in ei_b {
1310                        self.sub_variables(e, assigned_exprs);
1311                    }
1312                }
1313
1314                if let Some(inner) = eb {
1315                    for e in inner {
1316                        self.sub_variables(e, assigned_exprs);
1317                    }
1318                }
1319            },
1320            
1321            RynaExpr::CompiledLambda(_, _, _, _, _, _) |
1322            RynaExpr::Break(_) |
1323            RynaExpr::Continue(_) |
1324            RynaExpr::Literal(_, _) |
1325            RynaExpr::Macro(_, _, _, _, _, _) |
1326            RynaExpr::FunctionDefinition(_, _, _, _, _, _, _) |
1327            RynaExpr::PrefixOperatorDefinition(_, _, _) |
1328            RynaExpr::PostfixOperatorDefinition(_, _, _) |
1329            RynaExpr::BinaryOperatorDefinition(_, _, _, _) |
1330            RynaExpr::NaryOperatorDefinition(_, _, _, _) |
1331            RynaExpr::ClassDefinition(_, _, _, _, _, _, _) |
1332            RynaExpr::InterfaceDefinition(_, _, _, _, _, _, _, _) |
1333            RynaExpr::InterfaceImplementation(_, _, _, _, _) |
1334            RynaExpr::PrefixOperationDefinition(_, _, _, _, _, _, _, _) |
1335            RynaExpr::PostfixOperationDefinition(_, _, _, _, _, _, _, _) |
1336            RynaExpr::BinaryOperationDefinition(_, _, _, _, _, _, _, _) |
1337            RynaExpr::NaryOperationDefinition(_, _, _, _, _, _, _, _) => { },
1338
1339            e => unreachable!("{:?}", e)
1340        }
1341    }
1342
1343    fn remove_assignments(&self, exprs: &mut Vec<RynaExpr>, assigned_exprs: &mut FxHashMap<usize, RynaExpr>) {
1344        fn filter_assignments(exprs: &mut Vec<RynaExpr>, assigned_exprs: &mut FxHashMap<usize, RynaExpr>) {
1345            exprs.retain(|i| !matches!(i, RynaExpr::CompiledVariableDefinition(_, id, _, _, _, _) if assigned_exprs.contains_key(id)));
1346        }
1347
1348        filter_assignments(exprs, assigned_exprs);
1349
1350        for e in exprs {
1351            self.remove_assignments_expr(e, assigned_exprs);
1352        }
1353    }
1354
1355    fn remove_assignments_expr(&self, expr: &mut RynaExpr, assigned_exprs: &mut FxHashMap<usize, RynaExpr>) {
1356        match expr {
1357            RynaExpr::CompiledVariableDefinition(_, _, _, _, e, _) |
1358            RynaExpr::CompiledVariableAssignment(_, _, _, _, e, _) |
1359            RynaExpr::UnaryOperation(_, _, _, e) |
1360            RynaExpr::AttributeAccess(_, e, _) |
1361            RynaExpr::Return(_, e)  => self.remove_assignments_expr(e, assigned_exprs),
1362            
1363            RynaExpr::DoBlock(_, exprs, _) |
1364            RynaExpr::FunctionCall(_, _, _, exprs) |
1365            RynaExpr::Tuple(_, exprs) => self.remove_assignments(exprs, assigned_exprs),
1366
1367            RynaExpr::CompiledFor(_, _, _, _, c, exprs) |
1368            RynaExpr::While(_, c, exprs) => {
1369                self.remove_assignments_expr(c, assigned_exprs);
1370                self.remove_assignments(exprs, assigned_exprs);
1371            },
1372
1373            RynaExpr::NaryOperation(_, _, _, c, exprs) => {
1374                self.remove_assignments_expr(c, assigned_exprs);
1375                self.remove_assignments(exprs, assigned_exprs);
1376            },
1377
1378            RynaExpr::AttributeAssignment(_, a, b, _) |
1379            RynaExpr::BinaryOperation(_, _, _, a, b) => {
1380                self.remove_assignments_expr(a, assigned_exprs);
1381                self.remove_assignments_expr(b, assigned_exprs);
1382            },
1383
1384            RynaExpr::If(_, ic, ib, ei, eb) => {
1385                self.remove_assignments_expr(ic, assigned_exprs);
1386                self.remove_assignments(ib, assigned_exprs);
1387
1388                for (ei_h, ei_b) in ei {
1389                    self.remove_assignments_expr(ei_h, assigned_exprs);
1390                    self.remove_assignments(ei_b, assigned_exprs)
1391                }
1392
1393                if let Some(inner) = eb {
1394                    self.remove_assignments(inner, assigned_exprs);
1395                }
1396            },
1397
1398            RynaExpr::CompiledLambda(_, _, _, _, _, _) |
1399            RynaExpr::Variable(_, _, _, _, _) |
1400            RynaExpr::Break(_) |
1401            RynaExpr::Continue(_) |
1402            RynaExpr::Literal(_, _) |
1403            RynaExpr::Macro(_, _, _, _, _, _) |
1404            RynaExpr::FunctionDefinition(_, _, _, _, _, _, _) |
1405            RynaExpr::PrefixOperatorDefinition(_, _, _) |
1406            RynaExpr::PostfixOperatorDefinition(_, _, _) |
1407            RynaExpr::BinaryOperatorDefinition(_, _, _, _) |
1408            RynaExpr::NaryOperatorDefinition(_, _, _, _) |
1409            RynaExpr::ClassDefinition(_, _, _, _, _, _, _) |
1410            RynaExpr::InterfaceDefinition(_, _, _, _, _, _, _, _) |
1411            RynaExpr::InterfaceImplementation(_, _, _, _, _) |
1412            RynaExpr::PrefixOperationDefinition(_, _, _, _, _, _, _, _) |
1413            RynaExpr::PostfixOperationDefinition(_, _, _, _, _, _, _, _) |
1414            RynaExpr::BinaryOperationDefinition(_, _, _, _, _, _, _, _) |
1415            RynaExpr::NaryOperationDefinition(_, _, _, _, _, _, _, _) => { },
1416
1417            e => unreachable!("{:?}", e)
1418        }
1419    }
1420
1421    pub fn constant_propagation(&self, body: &mut Vec<RynaExpr>) {
1422        let mut var_usages = FxHashMap::default();
1423        let mut consts = FxHashMap::default();
1424        let mut assigned_exprs = FxHashMap::default();
1425
1426        // Compute constants
1427        for i in body.iter() {
1428            RynaContext::count_usages_expr(i, &mut var_usages, 1);
1429            self.get_constants(i, &mut consts, &mut assigned_exprs);
1430        }
1431
1432        // Filter by usages
1433        assigned_exprs.retain(|i, _| *consts.get(i).unwrap_or(&false) && *var_usages.get(i).unwrap_or(&0) == 1);
1434        
1435        // Sub variables
1436        for i in body.iter_mut() {
1437            self.sub_variables(i, &mut assigned_exprs);
1438        }
1439
1440        // Remove assignments
1441        self.remove_assignments(body, &mut assigned_exprs);
1442    }
1443
1444    pub fn late_optimize(&self, body: &mut Vec<RynaExpr>) {
1445        let mut var_offset = 0;
1446
1447        for line in body.iter() {
1448            RynaContext::max_variable(line, &mut var_offset);
1449        }
1450
1451        self.inline_functions(body, &mut var_offset);
1452        self.constant_propagation(body);
1453    }
1454}
1455
1456/*
1457    ╒════════════════════════╕
1458    │ Peephole optimizations │
1459    ╘════════════════════════╛
1460*/
1461
1462fn compute_labels(program: &mut [RynaInstruction]) {
1463    let mut labels = FxHashMap::default(); 
1464    let mut curr_idx = 0;
1465
1466    // Generate labels
1467    for (idx, i) in program.iter_mut().enumerate() {
1468        match &mut i.instruction {
1469            CompiledRynaExpr::Lambda(to, _, _, _) |
1470            CompiledRynaExpr::CallDestructor(to) |
1471            CompiledRynaExpr::Call(to) |
1472            CompiledRynaExpr::Jump(to) => {
1473                if !labels.contains_key(to) {
1474                    labels.entry(*to).or_insert(curr_idx);
1475                    *to = curr_idx;
1476                    curr_idx += 1;
1477
1478                } else {
1479                    *to = labels[to];
1480                }
1481            },
1482                    
1483            CompiledRynaExpr::RelativeJumpIfFalse(to, _) |
1484            CompiledRynaExpr::RelativeJumpIfTrue(to, _) => {
1485                let p = idx + *to;
1486
1487                if !labels.contains_key(&p) {
1488                    labels.entry(p).or_insert(curr_idx);
1489                    *to = curr_idx;
1490                    curr_idx += 1;
1491
1492                } else {
1493                    *to = labels[&p];
1494                }
1495            },
1496    
1497            CompiledRynaExpr::RelativeJump(to) => {
1498                let p = (idx as i32 + *to) as usize;
1499
1500                if !labels.contains_key(&p) {
1501                    labels.entry(p).or_insert(curr_idx);
1502                    *to = curr_idx as i32;
1503                    curr_idx += 1;
1504
1505                } else {
1506                    *to = labels[&p] as i32;
1507                }
1508            },
1509    
1510            _ => { }
1511        }
1512    }
1513
1514    // Insert labels
1515    for (line, tag) in &labels {
1516        program[*line].debug_info.labels.insert(*tag);
1517    }
1518}
1519
1520fn reassign_labels(program: &mut [RynaInstruction]) {
1521    let mut positions = FxHashMap::default(); 
1522
1523    // Generate label positions
1524    for (idx, i) in program.iter_mut().enumerate() {
1525        for l in &i.debug_info.labels {
1526            positions.entry(*l).or_insert(idx);
1527        }
1528
1529        i.debug_info.labels.clear();
1530    }
1531
1532    // Recompute positions
1533    for (idx, i) in program.iter_mut().enumerate() {
1534        match &mut i.instruction {
1535            CompiledRynaExpr::Lambda(to, _, _, _) |
1536            CompiledRynaExpr::Call(to) |
1537            CompiledRynaExpr::CallDestructor(to) |
1538            CompiledRynaExpr::Jump(to) => {
1539                *to = positions[to];
1540            },
1541                    
1542            CompiledRynaExpr::RelativeJumpIfFalse(to, _) |
1543            CompiledRynaExpr::RelativeJumpIfTrue(to, _) => {
1544                *to = positions[to] - idx;
1545            },
1546    
1547            CompiledRynaExpr::RelativeJump(to) => {
1548                *to = positions[&(*to as usize)] as i32 - idx as i32;
1549            },
1550    
1551            _ => { }
1552        }
1553    }
1554}
1555
1556impl RynaContext {
1557    fn peephole_optimization(&self, program: &mut Vec<RynaInstruction>) {
1558        use CompiledRynaExpr::*;
1559
1560        compute_labels(program);
1561
1562        let mut changed = true;
1563
1564        macro_rules! remove_instruction {
1565            ($idx: expr) => {
1566                let labels_to_remove = program[$idx].debug_info.labels.clone();
1567                program[$idx + 1].debug_info.labels.extend(&labels_to_remove);
1568                program.remove($idx);
1569            };
1570        }
1571
1572        while changed {
1573            changed = false;
1574
1575            // Look for optimizations
1576            for i in 0..(program.len() - 1) {
1577                macro_rules! change_first {
1578                    ($new_expr: expr) => {
1579                        program[i].instruction = $new_expr;
1580                        remove_instruction!(i + 1);
1581
1582                        changed = true;
1583                        break;
1584                    };
1585                }
1586
1587                macro_rules! change_second {
1588                    ($new_expr: expr) => {
1589                        program[i + 1].instruction = $new_expr;
1590                        remove_instruction!(i);
1591
1592                        changed = true;
1593                        break;
1594                    };
1595                }
1596
1597                macro_rules! remove_both {
1598                    () => {
1599                        remove_instruction!(i);
1600                        remove_instruction!(i);
1601
1602                        changed = true;
1603                        break;
1604                    };
1605                }
1606
1607                macro_rules! is_not_ref {
1608                    ($idx: expr) => {
1609                        {
1610                            let instr_t = &program[$idx].debug_info.var_type;
1611
1612                            instr_t.is_some() &&
1613                            !instr_t.as_ref().unwrap().is_ref()    
1614                        }
1615                    };
1616                }
1617                
1618                // Size 2
1619                match [&program[i].instruction, &program[i + 1].instruction] {
1620                    [Not, RelativeJumpIfFalse(offset, false)] => { change_second!(RelativeJumpIfTrue(*offset, false)); }
1621                    [Not, RelativeJumpIfTrue(offset, false)] => { change_second!(RelativeJumpIfFalse(*offset, false)); }
1622
1623                    [NativeFunctionCall(func_id, ov_id, type_args), Drop] => {
1624                        change_first!(NativeFunctionCallNoRet(*func_id, *ov_id, type_args.clone()));
1625                    }
1626
1627                    [UnaryOperatorCall(op_id, ov_id, type_args), Drop] => {
1628                        change_first!(UnaryOperatorCallNoRet(*op_id, *ov_id, type_args.clone()));
1629                    }
1630
1631                    [BinaryOperatorCall(op_id, ov_id, type_args), Drop] => {
1632                        change_first!(BinaryOperatorCallNoRet(*op_id, *ov_id, type_args.clone()));
1633                    }
1634
1635                    [Int(obj), StoreVariable(id, g)] => { change_second!(StoreIntVariable(*id, *g, obj.clone())); },
1636                    [Str(obj), StoreVariable(id, g)] => { change_second!(StoreStringVariable(*id, *g, obj.clone())); },
1637                    [Float(obj), StoreVariable(id, g)] => { change_second!(StoreFloatVariable(*id, *g, *obj)); },
1638                    [Bool(obj), StoreVariable(id, g)] => { change_second!(StoreBoolVariable(*id, *g, *obj)); },
1639
1640                    [GetVariable(id, g) | CloneVariable(id, g), Assign] if is_not_ref!(i) => { change_first!(AssignToVar(*id, *g)); },
1641                    [GetVariable(id, g) | CloneVariable(id, g), Assign] => { change_first!(AssignToVarDirect(*id, *g)); },
1642
1643                    [GetVariable(id, g) | CloneVariable(id, g), Demut] => { change_first!(RefVariable(*id, *g)); },
1644                    [GetVariable(id, g) | CloneVariable(id, g), Copy] => { change_first!(CopyVariable(*id, *g)); },
1645                    [RefVariable(id, g), Copy] => { change_first!(CopyVariable(*id, *g)); },
1646                    [GetVariable(id, g) | CloneVariable(id, g), Deref] => { change_first!(DerefVariable(*id, *g)); },
1647                    [RefVariable(id, g), Deref] => { change_first!(DerefVariable(*id, *g)); },
1648                    [GetVariable(id, g) | CloneVariable(id, g), Move] => { change_first!(MoveVariable(*id, *g)); },
1649                    
1650                    [AttributeMut(id), Demut] => { change_first!(AttributeRef(*id)); },
1651                    [AttributeMut(id), Copy] => { change_first!(AttributeCopy(*id)); },
1652                    [AttributeRef(id), Copy] => { change_first!(AttributeCopy(*id)); },
1653                    [AttributeMut(id), Deref] => { change_first!(AttributeDeref(*id)); },
1654                    [AttributeRef(id), Deref] => { change_first!(AttributeDeref(*id)); },
1655                    
1656                    [TupleElemMut(id), Demut] => { change_first!(TupleElemRef(*id)); },
1657                    [TupleElemMut(id), Copy] => { change_first!(TupleElemCopy(*id)); },
1658                    [TupleElemRef(id), Copy] => { change_first!(TupleElemCopy(*id)); },
1659                    [TupleElemMut(id), Deref] => { change_first!(TupleElemDeref(*id)); },
1660                    [TupleElemRef(id), Deref] => { change_first!(TupleElemDeref(*id)); },
1661                    
1662                    [IdxMut, Demut] => { change_first!(IdxRef); },
1663                    [IdxMut, Move] => { change_first!(IdxMoveRef); },
1664
1665                    [Not, Not] |
1666                    [Negi, Negi] |
1667                    [Negf, Negf] => { remove_both!(); }
1668                    
1669                    [Ref, Deref] |
1670                    [Mut, Deref] => { remove_both!(); }
1671
1672                    [Eqi, Not] => { change_first!(Neqi); },
1673                    [Eqf, Not] => { change_first!(Neqf); },
1674                    [Neqi, Not] => { change_first!(Eqi); },
1675                    [Neqf, Not] => { change_first!(Eqf); },
1676                    [Lti, Not] => { change_first!(Gteqi); },
1677                    [Ltf, Not] => { change_first!(Gteqf); },
1678                    [Gti, Not] => { change_first!(Lteqi); },
1679                    [Gtf, Not] => { change_first!(Lteqf); },
1680                    [Lteqi, Not] => { change_first!(Gti); },
1681                    [Lteqf, Not] => { change_first!(Gtf); },
1682                    [Gteqi, Not] => { change_first!(Lti); },
1683                    [Gteqf, Not] => { change_first!(Ltf); },
1684
1685                    [And, Not] => { change_first!(Nand); },
1686                    [Or, Not] => { change_first!(Nor); },
1687
1688                    // Flow optimizations
1689                    [StoreVariable(id_1, g_1), MoveVariable(id_2, g_2)] if id_1 == id_2 && g_1 == g_2 && is_not_ref!(i) => { remove_both!(); },
1690
1691                    _ => {}
1692                }
1693            }
1694        }
1695        
1696        reassign_labels(program);
1697    }
1698
1699    fn remove_empty_calls(&self, program: &mut Vec<RynaInstruction>) {
1700        use CompiledRynaExpr::*;
1701
1702        let mut lines_to_remove = vec!();
1703
1704        // Look for empty calls
1705        for (idx, i) in program.iter().enumerate() {
1706            match i.instruction {
1707                Call(loc) if program[loc].instruction == Return => {
1708                    lines_to_remove.push(idx);
1709                    lines_to_remove.push(loc);
1710                },
1711                _ => { }
1712            }
1713        }
1714
1715        lines_to_remove.sort();
1716        lines_to_remove.dedup();
1717
1718        // Remove lines
1719        compute_labels(program);
1720
1721        for line in lines_to_remove.into_iter().rev() {
1722            let other = program[line].debug_info.clone();
1723            program[line + 1].debug_info.merge_with(&other);
1724            program.remove(line);
1725        }
1726
1727        reassign_labels(program);
1728    }
1729
1730    fn remove_single_relative_jumps(&self, program: &mut Vec<RynaInstruction>) {
1731        use CompiledRynaExpr::*;
1732
1733        let mut lines_to_remove = vec!();
1734
1735        // Look for empty calls
1736        for (idx, i) in program.iter().enumerate() {
1737            if let RelativeJump(1) = i.instruction {
1738                lines_to_remove.push(idx);
1739            }
1740        }
1741
1742        lines_to_remove.sort();
1743        lines_to_remove.dedup();
1744
1745        // Remove lines
1746        compute_labels(program);
1747
1748        for line in lines_to_remove.into_iter().rev() {
1749            let other = program[line].debug_info.clone();
1750            program[line + 1].debug_info.merge_with(&other);
1751            program.remove(line);
1752        }
1753
1754        reassign_labels(program);
1755    }
1756
1757    fn remove_jump_chains(&self, program: &mut [RynaInstruction]) {
1758        use CompiledRynaExpr::*;
1759
1760        let mut changed = true;
1761
1762        while changed {
1763            changed = false;
1764            
1765            let mut increments = FxHashMap::default();
1766            let mut early_rets = FxHashSet::default();
1767
1768            // Look for jump chains
1769            for (idx, i) in program.iter().enumerate() {
1770                if let RelativeJump(loc) = i.instruction {
1771                    if let RelativeJump(loc_2) = program[(idx as i32 + loc) as usize].instruction {
1772                        increments.entry(idx).or_insert(loc_2);
1773                    
1774                    } else if let Return = program[(idx as i32 + loc) as usize].instruction {
1775                        early_rets.insert(idx);
1776                    }
1777                }
1778            }
1779
1780            // Apply skips
1781            for (idx, inc) in increments {
1782                if let RelativeJump(loc) = &mut program[idx].instruction {
1783                    *loc += inc;
1784                    changed = true;
1785                }
1786            }
1787
1788            for idx in early_rets {
1789                program[idx].instruction = Return;
1790                changed = true;
1791            }
1792        }
1793    }
1794
1795    fn tail_call_optimization(&self, program: &mut Vec<RynaInstruction>) {
1796        use CompiledRynaExpr::*;
1797
1798        compute_labels(program);
1799
1800        let mut changed = true;
1801
1802        while changed {
1803            changed = false;
1804            
1805            macro_rules! remove_instruction {
1806                ($idx: expr) => {
1807                    let other = program[$idx].debug_info.clone();
1808                    program[$idx + 1].debug_info.merge_with(&other);
1809                    program.remove($idx);
1810                };
1811            }
1812
1813            for i in 0..(program.len() - 1) {
1814                macro_rules! change_first {
1815                    ($new_expr: expr) => {
1816                        program[i].instruction = $new_expr;
1817                        remove_instruction!(i + 1);
1818    
1819                        changed = true;
1820                        break;
1821                    };
1822                }
1823                
1824                if let [Call(loc), Return] = [&program[i].instruction, &program[i + 1].instruction] {
1825                    change_first!(Jump(*loc));
1826                }
1827            }
1828        }
1829
1830        reassign_labels(program);
1831    }
1832}
1833
1834/*
1835    ╒══════════════════════╕
1836    │ Optimization routine │
1837    ╘══════════════════════╛
1838*/
1839
1840impl RynaContext {
1841    pub fn optimize_instructions(&self, program: &mut Vec<RynaInstruction>) {
1842        self.peephole_optimization(program);
1843        self.remove_single_relative_jumps(program);
1844        self.remove_empty_calls(program);
1845        self.remove_jump_chains(program);
1846        self.tail_call_optimization(program);
1847    }
1848}
1849
1850/*
1851    ╒═══════╕
1852    │ Tests │
1853    ╘═══════╛
1854*/
1855
1856#[cfg(test)]
1857mod tests {
1858    use crate::{compilation::{CompiledRynaExpr, RynaInstruction}, context::standard_ctx};
1859
1860    #[test]
1861    fn peephole_optimization() {
1862        let ctx = standard_ctx();
1863
1864        let mut program = vec!(
1865            RynaInstruction::from(CompiledRynaExpr::Jump(3)),
1866            RynaInstruction::from(CompiledRynaExpr::Jump(4)),
1867            RynaInstruction::from(CompiledRynaExpr::Jump(5)),
1868            RynaInstruction::from(CompiledRynaExpr::Jump(6)),
1869            RynaInstruction::from(CompiledRynaExpr::Not),
1870            RynaInstruction::from(CompiledRynaExpr::RelativeJumpIfTrue(2, false)),
1871            RynaInstruction::from(CompiledRynaExpr::Empty),
1872            RynaInstruction::from(CompiledRynaExpr::Jump(4)),
1873            RynaInstruction::from(CompiledRynaExpr::Jump(5)),
1874            RynaInstruction::from(CompiledRynaExpr::Jump(6)),
1875            RynaInstruction::from(CompiledRynaExpr::Jump(7)),
1876            RynaInstruction::from(CompiledRynaExpr::Halt)
1877        );
1878
1879        ctx.peephole_optimization(&mut program);
1880
1881        assert_eq!(
1882            program,
1883            vec!(
1884                RynaInstruction::from(CompiledRynaExpr::Jump(3)),
1885                RynaInstruction::from(CompiledRynaExpr::Jump(4)),
1886                RynaInstruction::from(CompiledRynaExpr::Jump(4)),
1887                RynaInstruction::from(CompiledRynaExpr::Jump(5)),
1888                RynaInstruction::from(CompiledRynaExpr::RelativeJumpIfFalse(2, false)),
1889                RynaInstruction::from(CompiledRynaExpr::Empty),
1890                RynaInstruction::from(CompiledRynaExpr::Jump(4)),
1891                RynaInstruction::from(CompiledRynaExpr::Jump(4)),
1892                RynaInstruction::from(CompiledRynaExpr::Jump(5)),
1893                RynaInstruction::from(CompiledRynaExpr::Jump(6)),
1894                RynaInstruction::from(CompiledRynaExpr::Halt)
1895            )
1896        )
1897    }
1898}
ryna/optimization.rs

ryna/
optimization.rs
