nessa/
optimization.rs

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

nessa/
optimization.rs
