oxilean_codegen/opt_regalloc/
functions.rs

1//! Auto-generated module
2//!
3//! 🤖 Generated with [SplitRS](https://github.com/cool-japan/splitrs)
4
5use crate::lcnf::{LcnfArg, LcnfExpr, LcnfFunDecl, LcnfLetValue, LcnfType, LcnfVarId};
6use std::collections::{HashMap, HashSet, VecDeque};
7
8use super::types::{
9    Allocation, GraphColoringAllocator, InterferenceGraph, LinearScanAllocator, LiveInterval,
10    PhysReg, RAAnalysisCache, RAConstantFoldingHelper, RADepGraph, RADominatorTree, RAExtCache,
11    RAExtConstFolder, RAExtDepGraph, RAExtDomTree, RAExtLiveness, RAExtPassConfig, RAExtPassPhase,
12    RAExtPassRegistry, RAExtPassStats, RAExtWorklist, RALivenessInfo, RAPassConfig, RAPassPhase,
13    RAPassRegistry, RAPassStats, RAWorklist, RegAllocConfig, RegAllocDiagCollector,
14    RegAllocDiagMsg, RegAllocEmitStats, RegAllocEventLog, RegAllocFeatures, RegAllocIdGen,
15    RegAllocIncrKey, RegAllocNameScope, RegAllocPass, RegAllocPassTiming, RegAllocProfiler,
16    RegAllocReport, RegAllocSourceBuffer, RegAllocVersion, RegClass, SpillSlot, VirtualReg,
17};
18
19/// Walk an LCNF expression tree and populate live intervals.
20pub(super) fn collect_intervals_from_expr(
21    expr: &LcnfExpr,
22    counter: &mut u32,
23    intervals: &mut HashMap<LcnfVarId, LiveInterval>,
24) {
25    match expr {
26        LcnfExpr::Let {
27            id, value, body, ..
28        } => {
29            let pos = *counter;
30            *counter += 1;
31            let iv = intervals
32                .entry(*id)
33                .or_insert_with(|| LiveInterval::new(*id, pos, pos + 1));
34            iv.add_def(pos);
35            record_uses_in_value(value, pos, intervals);
36            collect_intervals_from_expr(body, counter, intervals);
37        }
38        LcnfExpr::Case {
39            scrutinee,
40            alts,
41            default,
42            ..
43        } => {
44            let pos = *counter;
45            *counter += 1;
46            record_use(*scrutinee, pos, intervals);
47            for alt in alts {
48                for param in &alt.params {
49                    let iv = intervals
50                        .entry(param.id)
51                        .or_insert_with(|| LiveInterval::new(param.id, pos, pos + 1));
52                    iv.add_def(pos);
53                }
54                collect_intervals_from_expr(&alt.body, counter, intervals);
55            }
56            if let Some(def) = default {
57                collect_intervals_from_expr(def, counter, intervals);
58            }
59        }
60        LcnfExpr::Return(arg) => {
61            let pos = *counter;
62            *counter += 1;
63            if let LcnfArg::Var(id) = arg {
64                record_use(*id, pos, intervals);
65            }
66        }
67        LcnfExpr::TailCall(func, args) => {
68            let pos = *counter;
69            *counter += 1;
70            if let LcnfArg::Var(id) = func {
71                record_use(*id, pos, intervals);
72            }
73            for arg in args {
74                if let LcnfArg::Var(id) = arg {
75                    record_use(*id, pos, intervals);
76                }
77            }
78        }
79        LcnfExpr::Unreachable => {}
80    }
81}
82pub(super) fn record_use(
83    id: LcnfVarId,
84    pos: u32,
85    intervals: &mut HashMap<LcnfVarId, LiveInterval>,
86) {
87    let iv = intervals
88        .entry(id)
89        .or_insert_with(|| LiveInterval::new(id, pos, pos + 1));
90    iv.add_use(pos);
91}
92pub(super) fn record_uses_in_value(
93    value: &LcnfLetValue,
94    pos: u32,
95    intervals: &mut HashMap<LcnfVarId, LiveInterval>,
96) {
97    match value {
98        LcnfLetValue::App(func, args) => {
99            if let LcnfArg::Var(id) = func {
100                record_use(*id, pos, intervals);
101            }
102            for arg in args {
103                if let LcnfArg::Var(id) = arg {
104                    record_use(*id, pos, intervals);
105                }
106            }
107        }
108        LcnfLetValue::Ctor(_, _, args) | LcnfLetValue::Reuse(_, _, _, args) => {
109            for arg in args {
110                if let LcnfArg::Var(id) = arg {
111                    record_use(*id, pos, intervals);
112                }
113            }
114        }
115        LcnfLetValue::Proj(_, _, src) => {
116            record_use(*src, pos, intervals);
117        }
118        LcnfLetValue::FVar(id) | LcnfLetValue::Reset(id) => {
119            record_use(*id, pos, intervals);
120        }
121        LcnfLetValue::Lit(_) | LcnfLetValue::Erased => {}
122    }
123}
124/// Compute a canonical (post-coalescing) representative for each vreg.
125pub fn compute_canonical_map(
126    merge_pairs: &[(LcnfVarId, LcnfVarId)],
127) -> HashMap<LcnfVarId, LcnfVarId> {
128    let mut parent: HashMap<LcnfVarId, LcnfVarId> = HashMap::new();
129    for &(u, v) in merge_pairs {
130        let ru = find(&mut parent, u);
131        let rv = find(&mut parent, v);
132        if ru != rv {
133            parent.insert(rv, ru);
134        }
135    }
136    let keys: Vec<LcnfVarId> = parent.keys().copied().collect();
137    let mut canonical: HashMap<LcnfVarId, LcnfVarId> = HashMap::new();
138    for k in keys {
139        let root = find(&mut parent, k);
140        canonical.insert(k, root);
141    }
142    canonical
143}
144/// Union-Find `find` with path compression.
145pub(super) fn find(parent: &mut HashMap<LcnfVarId, LcnfVarId>, mut x: LcnfVarId) -> LcnfVarId {
146    let mut path = Vec::new();
147    while let Some(&p) = parent.get(&x) {
148        if p == x {
149            break;
150        }
151        path.push(x);
152        x = p;
153    }
154    for node in path {
155        parent.insert(node, x);
156    }
157    x
158}
159/// Build a BFS-order instruction numbering for an LCNF expression.
160pub fn number_instructions(decl: &LcnfFunDecl) -> HashMap<LcnfVarId, u32> {
161    let mut numbering = HashMap::new();
162    let mut counter = 0u32;
163    for param in &decl.params {
164        numbering.insert(param.id, counter);
165        counter += 1;
166    }
167    number_expr(&decl.body, &mut counter, &mut numbering);
168    numbering
169}
170pub(super) fn number_expr(
171    expr: &LcnfExpr,
172    counter: &mut u32,
173    numbering: &mut HashMap<LcnfVarId, u32>,
174) {
175    match expr {
176        LcnfExpr::Let { id, body, .. } => {
177            numbering.insert(*id, *counter);
178            *counter += 1;
179            number_expr(body, counter, numbering);
180        }
181        LcnfExpr::Case { alts, default, .. } => {
182            *counter += 1;
183            for alt in alts {
184                for param in &alt.params {
185                    numbering.insert(param.id, *counter);
186                }
187                *counter += 1;
188                number_expr(&alt.body, counter, numbering);
189            }
190            if let Some(def) = default {
191                number_expr(def, counter, numbering);
192            }
193        }
194        LcnfExpr::Return(_) | LcnfExpr::TailCall(_, _) | LcnfExpr::Unreachable => {
195            *counter += 1;
196        }
197    }
198}
199/// Collect all vreg IDs used in a declaration (body + params).
200pub fn collect_vregs(decl: &LcnfFunDecl) -> Vec<LcnfVarId> {
201    let mut seen = HashSet::new();
202    let mut result = Vec::new();
203    for param in &decl.params {
204        if seen.insert(param.id) {
205            result.push(param.id);
206        }
207    }
208    collect_vregs_from_expr(&decl.body, &mut seen, &mut result);
209    result
210}
211pub(super) fn collect_vregs_from_expr(
212    expr: &LcnfExpr,
213    seen: &mut HashSet<LcnfVarId>,
214    result: &mut Vec<LcnfVarId>,
215) {
216    let mut worklist: VecDeque<&LcnfExpr> = VecDeque::new();
217    worklist.push_back(expr);
218    while let Some(e) = worklist.pop_front() {
219        match e {
220            LcnfExpr::Let { id, body, .. } => {
221                if seen.insert(*id) {
222                    result.push(*id);
223                }
224                worklist.push_back(body);
225            }
226            LcnfExpr::Case { alts, default, .. } => {
227                for alt in alts {
228                    for param in &alt.params {
229                        if seen.insert(param.id) {
230                            result.push(param.id);
231                        }
232                    }
233                    worklist.push_back(&alt.body);
234                }
235                if let Some(def) = default {
236                    worklist.push_back(def);
237                }
238            }
239            LcnfExpr::Return(_) | LcnfExpr::TailCall(_, _) | LcnfExpr::Unreachable => {}
240        }
241    }
242}
243#[cfg(test)]
244mod tests {
245    use super::*;
246    use crate::lcnf::{
247        LcnfArg, LcnfExpr, LcnfFunDecl, LcnfLetValue, LcnfLit, LcnfParam, LcnfType, LcnfVarId,
248    };
249    pub(super) fn v(n: u64) -> LcnfVarId {
250        LcnfVarId(n)
251    }
252    pub(super) fn make_param(n: u64, name: &str) -> LcnfParam {
253        LcnfParam {
254            id: v(n),
255            name: name.to_string(),
256            ty: LcnfType::Nat,
257            erased: false,
258            borrowed: false,
259        }
260    }
261    pub(super) fn make_decl(name: &str, params: Vec<LcnfParam>, body: LcnfExpr) -> LcnfFunDecl {
262        LcnfFunDecl {
263            name: name.to_string(),
264            original_name: None,
265            params,
266            ret_type: LcnfType::Nat,
267            body,
268            is_recursive: false,
269            is_lifted: false,
270            inline_cost: 1,
271        }
272    }
273    pub(super) fn ret_var(n: u64) -> LcnfExpr {
274        LcnfExpr::Return(LcnfArg::Var(v(n)))
275    }
276    pub(super) fn let_nat(id: u64, body: LcnfExpr) -> LcnfExpr {
277        LcnfExpr::Let {
278            id: v(id),
279            name: format!("x{}", id),
280            ty: LcnfType::Nat,
281            value: LcnfLetValue::Lit(LcnfLit::Nat(id)),
282            body: Box::new(body),
283        }
284    }
285    #[test]
286    pub(super) fn test_reg_class_prefix() {
287        assert_eq!(RegClass::Integer.prefix(), "r");
288        assert_eq!(RegClass::Float.prefix(), "f");
289        assert_eq!(RegClass::Vector.prefix(), "v");
290        assert_eq!(RegClass::Predicate.prefix(), "p");
291    }
292    #[test]
293    pub(super) fn test_phys_reg_integer_bank() {
294        let bank = PhysReg::integer_bank(4);
295        assert_eq!(bank.len(), 4);
296        assert_eq!(bank[0].name, "r0");
297        assert_eq!(bank[3].name, "r3");
298        assert!(bank.iter().all(|r| r.class == RegClass::Integer));
299    }
300    #[test]
301    pub(super) fn test_phys_reg_float_bank() {
302        let bank = PhysReg::float_bank(2);
303        assert_eq!(bank.len(), 2);
304        assert_eq!(bank[0].name, "f0");
305        assert_eq!(bank[0].class, RegClass::Float);
306    }
307    #[test]
308    pub(super) fn test_virtual_reg_class_nat() {
309        let vr = VirtualReg::new(0, LcnfType::Nat);
310        assert_eq!(vr.reg_class(), RegClass::Integer);
311    }
312    #[test]
313    pub(super) fn test_virtual_reg_with_hint() {
314        let hint = PhysReg::new(0, "r0", RegClass::Integer);
315        let vr = VirtualReg::with_hint(1, LcnfType::Nat, hint.clone());
316        assert_eq!(vr.hint, Some(hint));
317    }
318    #[test]
319    pub(super) fn test_live_interval_overlaps_true() {
320        let a = LiveInterval::new(v(1), 0, 5);
321        let b = LiveInterval::new(v(2), 3, 8);
322        assert!(a.overlaps(&b));
323    }
324    #[test]
325    pub(super) fn test_live_interval_overlaps_false() {
326        let a = LiveInterval::new(v(1), 0, 3);
327        let b = LiveInterval::new(v(2), 5, 8);
328        assert!(!a.overlaps(&b));
329    }
330    #[test]
331    pub(super) fn test_live_interval_adjacent_no_overlap() {
332        let a = LiveInterval::new(v(1), 0, 3);
333        let b = LiveInterval::new(v(2), 3, 6);
334        assert!(!a.overlaps(&b));
335    }
336    #[test]
337    pub(super) fn test_live_interval_length() {
338        let iv = LiveInterval::new(v(1), 2, 7);
339        assert_eq!(iv.length(), 5);
340    }
341    #[test]
342    pub(super) fn test_live_interval_add_use_extends_end() {
343        let mut iv = LiveInterval::new(v(1), 0, 3);
344        iv.add_use(10);
345        assert_eq!(iv.end, 11);
346    }
347    #[test]
348    pub(super) fn test_live_interval_spill_weight() {
349        let mut iv = LiveInterval::new(v(1), 0, 10);
350        iv.add_use(2);
351        iv.add_use(5);
352        iv.add_use(8);
353        iv.compute_spill_weight();
354        assert!(iv.spill_weight > 0.0);
355    }
356    #[test]
357    pub(super) fn test_interference_graph_add_edge() {
358        let mut g = InterferenceGraph::new();
359        g.add_edge(v(1), v(2));
360        assert!(g.interferes(v(1), v(2)));
361        assert!(g.interferes(v(2), v(1)));
362    }
363    #[test]
364    pub(super) fn test_interference_graph_no_self_loop() {
365        let mut g = InterferenceGraph::new();
366        g.add_edge(v(1), v(1));
367        assert!(!g.interferes(v(1), v(1)));
368    }
369    #[test]
370    pub(super) fn test_interference_graph_degree() {
371        let mut g = InterferenceGraph::new();
372        g.add_edge(v(1), v(2));
373        g.add_edge(v(1), v(3));
374        assert_eq!(g.degree(v(1)), 2);
375    }
376    #[test]
377    pub(super) fn test_interference_graph_remove_node() {
378        let mut g = InterferenceGraph::new();
379        g.add_edge(v(1), v(2));
380        g.remove_node(v(1));
381        assert!(!g.nodes.contains(&v(1)));
382        assert!(!g.interferes(v(2), v(1)));
383    }
384    #[test]
385    pub(super) fn test_interference_graph_from_intervals() {
386        let ivs = vec![
387            LiveInterval::new(v(1), 0, 5),
388            LiveInterval::new(v(2), 3, 8),
389            LiveInterval::new(v(3), 6, 10),
390        ];
391        let g = InterferenceGraph::build_from_intervals(&ivs);
392        assert!(g.interferes(v(1), v(2)));
393        assert!(g.interferes(v(2), v(3)));
394        assert!(!g.interferes(v(1), v(3)));
395    }
396    #[test]
397    pub(super) fn test_linear_scan_simple() {
398        let regs = PhysReg::integer_bank(4);
399        let mut lsa = LinearScanAllocator::new(regs);
400        let decl = make_decl("f", vec![], let_nat(1, let_nat(2, ret_var(2))));
401        let intervals = lsa.build_live_intervals(&decl);
402        let alloc = lsa.linear_scan(intervals, 4);
403        assert_eq!(alloc.spills.len(), 0);
404    }
405    #[test]
406    pub(super) fn test_linear_scan_spills_when_pressure() {
407        let regs = PhysReg::integer_bank(1);
408        let mut lsa = LinearScanAllocator::new(regs);
409        let body = let_nat(
410            1,
411            let_nat(
412                2,
413                let_nat(3, let_nat(4, LcnfExpr::Return(LcnfArg::Var(v(1))))),
414            ),
415        );
416        let decl = make_decl("g", vec![], body);
417        let intervals = lsa.build_live_intervals(&decl);
418        let alloc = lsa.linear_scan(intervals, 1);
419        assert!(alloc.spills.len() > 0 || alloc.reg_map.len() <= 1);
420    }
421    #[test]
422    pub(super) fn test_linear_scan_build_intervals_with_params() {
423        let regs = PhysReg::integer_bank(4);
424        let lsa = LinearScanAllocator::new(regs);
425        let params = vec![make_param(0, "a"), make_param(1, "b")];
426        let decl = make_decl("h", params, ret_var(0));
427        let intervals = lsa.build_live_intervals(&decl);
428        assert!(intervals.iter().any(|iv| iv.vreg == v(0)));
429    }
430    #[test]
431    pub(super) fn test_graph_coloring_simple() {
432        let regs = PhysReg::integer_bank(3);
433        let mut gca = GraphColoringAllocator::new(regs);
434        let ivs = vec![
435            LiveInterval::new(v(1), 0, 3),
436            LiveInterval::new(v(2), 4, 7),
437            LiveInterval::new(v(3), 8, 11),
438        ];
439        let alloc = gca.allocate(&ivs);
440        assert_eq!(alloc.spills.len(), 0);
441        assert_eq!(alloc.reg_map.len(), 3);
442    }
443    #[test]
444    pub(super) fn test_graph_coloring_interfering() {
445        let regs = PhysReg::integer_bank(2);
446        let mut gca = GraphColoringAllocator::new(regs);
447        let ivs = vec![
448            LiveInterval::new(v(1), 0, 10),
449            LiveInterval::new(v(2), 0, 10),
450            LiveInterval::new(v(3), 0, 10),
451        ];
452        let alloc = gca.allocate(&ivs);
453        assert!(alloc.spills.len() >= 1 || alloc.reg_map.len() <= 2);
454    }
455    #[test]
456    pub(super) fn test_graph_coloring_simplify_removes_nodes() {
457        let regs = PhysReg::integer_bank(4);
458        let mut gca = GraphColoringAllocator::new(regs);
459        let ivs = vec![LiveInterval::new(v(1), 0, 3), LiveInterval::new(v(2), 4, 7)];
460        gca.build_interference_graph(&ivs);
461        let removed = gca.simplify();
462        assert!(removed >= 1);
463    }
464    #[test]
465    pub(super) fn test_regalloc_pass_linear_scan() {
466        let mut pass = RegAllocPass::new(4);
467        let decl = make_decl("fn_ls", vec![], let_nat(1, ret_var(1)));
468        let mut decls = vec![decl];
469        pass.run(&mut decls);
470        let r = pass.report();
471        assert_eq!(r.functions_processed, 1);
472        assert!(r.vregs_allocated >= 1);
473    }
474    #[test]
475    pub(super) fn test_regalloc_pass_graph_coloring() {
476        let mut pass = RegAllocPass::graph_coloring(4);
477        let decl = make_decl("fn_gc", vec![], let_nat(1, let_nat(2, ret_var(2))));
478        let mut decls = vec![decl];
479        pass.run(&mut decls);
480        let r = pass.report();
481        assert_eq!(r.functions_processed, 1);
482    }
483    #[test]
484    pub(super) fn test_regalloc_pass_allocation_stored() {
485        let mut pass = RegAllocPass::new(4);
486        let decl = make_decl("my_fn", vec![], let_nat(5, ret_var(5)));
487        let mut decls = vec![decl];
488        pass.run(&mut decls);
489        assert!(pass.allocation_for("my_fn").is_some());
490    }
491    #[test]
492    pub(super) fn test_regalloc_pass_spill_ratio() {
493        let r = RegAllocReport {
494            vregs_allocated: 7,
495            spills: 3,
496            ..Default::default()
497        };
498        assert!((r.spill_ratio() - 0.3).abs() < 1e-6);
499    }
500    #[test]
501    pub(super) fn test_regalloc_pass_empty() {
502        let mut pass = RegAllocPass::new(4);
503        let mut decls = vec![];
504        pass.run(&mut decls);
505        let r = pass.report();
506        assert_eq!(r.functions_processed, 0);
507        assert_eq!(r.spills, 0);
508    }
509    #[test]
510    pub(super) fn test_spill_slot_new() {
511        let s = SpillSlot::new(v(1), 16, 8);
512        assert_eq!(s.offset, 16);
513        assert_eq!(s.size, 8);
514        assert_eq!(s.vreg, v(1));
515    }
516    #[test]
517    pub(super) fn test_allocation_assign_lookup() {
518        let mut alloc = Allocation::new();
519        let pr = PhysReg::new(0, "r0", RegClass::Integer);
520        alloc.assign(v(1), pr.clone());
521        assert_eq!(alloc.lookup(v(1)), Some(&pr));
522    }
523    #[test]
524    pub(super) fn test_allocation_spill() {
525        let mut alloc = Allocation::new();
526        alloc.spill(v(2), 8);
527        assert!(alloc.is_spilled(v(2)));
528        assert_eq!(alloc.stack_frame_size(), 8);
529    }
530    #[test]
531    pub(super) fn test_compute_canonical_map() {
532        let pairs = vec![(v(1), v(2)), (v(2), v(3))];
533        let canonical = compute_canonical_map(&pairs);
534        assert_eq!(canonical.get(&v(2)), canonical.get(&v(2)));
535    }
536    #[test]
537    pub(super) fn test_collect_vregs() {
538        let body = let_nat(10, let_nat(11, ret_var(10)));
539        let decl = make_decl("f", vec![make_param(0, "x")], body);
540        let vregs = collect_vregs(&decl);
541        assert!(vregs.contains(&v(0)));
542        assert!(vregs.contains(&v(10)));
543        assert!(vregs.contains(&v(11)));
544    }
545    #[test]
546    pub(super) fn test_number_instructions() {
547        let body = let_nat(1, let_nat(2, ret_var(1)));
548        let decl = make_decl("f", vec![], body);
549        let numbering = number_instructions(&decl);
550        assert!(numbering.contains_key(&v(1)));
551        assert!(numbering.contains_key(&v(2)));
552        assert!(numbering[&v(1)] < numbering[&v(2)]);
553    }
554}
555#[cfg(test)]
556mod tests_reg_alloc_extra {
557    use super::*;
558    #[test]
559    pub(super) fn test_reg_alloc_config() {
560        let mut cfg = RegAllocConfig::new();
561        cfg.set("mode", "release");
562        cfg.set("verbose", "true");
563        assert_eq!(cfg.get("mode"), Some("release"));
564        assert!(cfg.get_bool("verbose"));
565        assert!(cfg.get_int("mode").is_none());
566        assert_eq!(cfg.len(), 2);
567    }
568    #[test]
569    pub(super) fn test_reg_alloc_source_buffer() {
570        let mut buf = RegAllocSourceBuffer::new();
571        buf.push_line("fn main() {");
572        buf.indent();
573        buf.push_line("println!(\"hello\");");
574        buf.dedent();
575        buf.push_line("}");
576        assert!(buf.as_str().contains("fn main()"));
577        assert!(buf.as_str().contains("    println!"));
578        assert_eq!(buf.line_count(), 3);
579        buf.reset();
580        assert!(buf.is_empty());
581    }
582    #[test]
583    pub(super) fn test_reg_alloc_name_scope() {
584        let mut scope = RegAllocNameScope::new();
585        assert!(scope.declare("x"));
586        assert!(!scope.declare("x"));
587        assert!(scope.is_declared("x"));
588        let scope = scope.push_scope();
589        assert_eq!(scope.depth(), 1);
590        let mut scope = scope.pop_scope();
591        assert_eq!(scope.depth(), 0);
592        scope.declare("y");
593        assert_eq!(scope.len(), 2);
594    }
595    #[test]
596    pub(super) fn test_reg_alloc_diag_collector() {
597        let mut col = RegAllocDiagCollector::new();
598        col.emit(RegAllocDiagMsg::warning("pass_a", "slow"));
599        col.emit(RegAllocDiagMsg::error("pass_b", "fatal"));
600        assert!(col.has_errors());
601        assert_eq!(col.errors().len(), 1);
602        assert_eq!(col.warnings().len(), 1);
603        col.clear();
604        assert!(col.is_empty());
605    }
606    #[test]
607    pub(super) fn test_reg_alloc_id_gen() {
608        let mut gen = RegAllocIdGen::new();
609        assert_eq!(gen.next_id(), 0);
610        assert_eq!(gen.next_id(), 1);
611        gen.skip(10);
612        assert_eq!(gen.next_id(), 12);
613        gen.reset();
614        assert_eq!(gen.peek_next(), 0);
615    }
616    #[test]
617    pub(super) fn test_reg_alloc_incr_key() {
618        let k1 = RegAllocIncrKey::new(100, 200);
619        let k2 = RegAllocIncrKey::new(100, 200);
620        let k3 = RegAllocIncrKey::new(999, 200);
621        assert!(k1.matches(&k2));
622        assert!(!k1.matches(&k3));
623    }
624    #[test]
625    pub(super) fn test_reg_alloc_profiler() {
626        let mut p = RegAllocProfiler::new();
627        p.record(RegAllocPassTiming::new("pass_a", 1000, 50, 200, 100));
628        p.record(RegAllocPassTiming::new("pass_b", 500, 30, 100, 200));
629        assert_eq!(p.total_elapsed_us(), 1500);
630        assert_eq!(
631            p.slowest_pass()
632                .expect("slowest pass should exist")
633                .pass_name,
634            "pass_a"
635        );
636        assert_eq!(p.profitable_passes().len(), 1);
637    }
638    #[test]
639    pub(super) fn test_reg_alloc_event_log() {
640        let mut log = RegAllocEventLog::new(3);
641        log.push("event1");
642        log.push("event2");
643        log.push("event3");
644        assert_eq!(log.len(), 3);
645        log.push("event4");
646        assert_eq!(log.len(), 3);
647        assert_eq!(
648            log.iter()
649                .next()
650                .expect("iterator should have next element"),
651            "event2"
652        );
653    }
654    #[test]
655    pub(super) fn test_reg_alloc_version() {
656        let v = RegAllocVersion::new(1, 2, 3).with_pre("alpha");
657        assert!(!v.is_stable());
658        assert_eq!(format!("{}", v), "1.2.3-alpha");
659        let stable = RegAllocVersion::new(2, 0, 0);
660        assert!(stable.is_stable());
661        assert!(stable.is_compatible_with(&RegAllocVersion::new(2, 0, 0)));
662        assert!(!stable.is_compatible_with(&RegAllocVersion::new(3, 0, 0)));
663    }
664    #[test]
665    pub(super) fn test_reg_alloc_features() {
666        let mut f = RegAllocFeatures::new();
667        f.enable("sse2");
668        f.enable("avx2");
669        assert!(f.is_enabled("sse2"));
670        assert!(!f.is_enabled("avx512"));
671        f.disable("avx2");
672        assert!(!f.is_enabled("avx2"));
673        let mut g = RegAllocFeatures::new();
674        g.enable("sse2");
675        g.enable("neon");
676        let union = f.union(&g);
677        assert!(union.is_enabled("sse2") && union.is_enabled("neon"));
678        let inter = f.intersection(&g);
679        assert!(inter.is_enabled("sse2"));
680    }
681    #[test]
682    pub(super) fn test_reg_alloc_emit_stats() {
683        let mut s = RegAllocEmitStats::new();
684        s.bytes_emitted = 50_000;
685        s.items_emitted = 500;
686        s.elapsed_ms = 100;
687        assert!(s.is_clean());
688        assert!((s.throughput_bps() - 500_000.0).abs() < 1.0);
689        let disp = format!("{}", s);
690        assert!(disp.contains("bytes=50000"));
691    }
692}
693#[cfg(test)]
694mod RA_infra_tests {
695    use super::*;
696    #[test]
697    pub(super) fn test_pass_config() {
698        let config = RAPassConfig::new("test_pass", RAPassPhase::Transformation);
699        assert!(config.enabled);
700        assert!(config.phase.is_modifying());
701        assert_eq!(config.phase.name(), "transformation");
702    }
703    #[test]
704    pub(super) fn test_pass_stats() {
705        let mut stats = RAPassStats::new();
706        stats.record_run(10, 100, 3);
707        stats.record_run(20, 200, 5);
708        assert_eq!(stats.total_runs, 2);
709        assert!((stats.average_changes_per_run() - 15.0).abs() < 0.01);
710        assert!((stats.success_rate() - 1.0).abs() < 0.01);
711        let s = stats.format_summary();
712        assert!(s.contains("Runs: 2/2"));
713    }
714    #[test]
715    pub(super) fn test_pass_registry() {
716        let mut reg = RAPassRegistry::new();
717        reg.register(RAPassConfig::new("pass_a", RAPassPhase::Analysis));
718        reg.register(RAPassConfig::new("pass_b", RAPassPhase::Transformation).disabled());
719        assert_eq!(reg.total_passes(), 2);
720        assert_eq!(reg.enabled_count(), 1);
721        reg.update_stats("pass_a", 5, 50, 2);
722        let stats = reg.get_stats("pass_a").expect("stats should exist");
723        assert_eq!(stats.total_changes, 5);
724    }
725    #[test]
726    pub(super) fn test_analysis_cache() {
727        let mut cache = RAAnalysisCache::new(10);
728        cache.insert("key1".to_string(), vec![1, 2, 3]);
729        assert!(cache.get("key1").is_some());
730        assert!(cache.get("key2").is_none());
731        assert!((cache.hit_rate() - 0.5).abs() < 0.01);
732        cache.invalidate("key1");
733        assert!(!cache.entries["key1"].valid);
734        assert_eq!(cache.size(), 1);
735    }
736    #[test]
737    pub(super) fn test_worklist() {
738        let mut wl = RAWorklist::new();
739        assert!(wl.push(1));
740        assert!(wl.push(2));
741        assert!(!wl.push(1));
742        assert_eq!(wl.len(), 2);
743        assert_eq!(wl.pop(), Some(1));
744        assert!(!wl.contains(1));
745        assert!(wl.contains(2));
746    }
747    #[test]
748    pub(super) fn test_dominator_tree() {
749        let mut dt = RADominatorTree::new(5);
750        dt.set_idom(1, 0);
751        dt.set_idom(2, 0);
752        dt.set_idom(3, 1);
753        assert!(dt.dominates(0, 3));
754        assert!(dt.dominates(1, 3));
755        assert!(!dt.dominates(2, 3));
756        assert!(dt.dominates(3, 3));
757    }
758    #[test]
759    pub(super) fn test_liveness() {
760        let mut liveness = RALivenessInfo::new(3);
761        liveness.add_def(0, 1);
762        liveness.add_use(1, 1);
763        assert!(liveness.defs[0].contains(&1));
764        assert!(liveness.uses[1].contains(&1));
765    }
766    #[test]
767    pub(super) fn test_constant_folding() {
768        assert_eq!(RAConstantFoldingHelper::fold_add_i64(3, 4), Some(7));
769        assert_eq!(RAConstantFoldingHelper::fold_div_i64(10, 0), None);
770        assert_eq!(RAConstantFoldingHelper::fold_div_i64(10, 2), Some(5));
771        assert_eq!(
772            RAConstantFoldingHelper::fold_bitand_i64(0b1100, 0b1010),
773            0b1000
774        );
775        assert_eq!(RAConstantFoldingHelper::fold_bitnot_i64(0), -1);
776    }
777    #[test]
778    pub(super) fn test_dep_graph() {
779        let mut g = RADepGraph::new();
780        g.add_dep(1, 2);
781        g.add_dep(2, 3);
782        g.add_dep(1, 3);
783        assert_eq!(g.dependencies_of(2), vec![1]);
784        let topo = g.topological_sort();
785        assert_eq!(topo.len(), 3);
786        assert!(!g.has_cycle());
787        let pos: std::collections::HashMap<u32, usize> =
788            topo.iter().enumerate().map(|(i, &n)| (n, i)).collect();
789        assert!(pos[&1] < pos[&2]);
790        assert!(pos[&1] < pos[&3]);
791        assert!(pos[&2] < pos[&3]);
792    }
793}
794#[cfg(test)]
795mod raext_pass_tests {
796    use super::*;
797    #[test]
798    pub(super) fn test_raext_phase_order() {
799        assert_eq!(RAExtPassPhase::Early.order(), 0);
800        assert_eq!(RAExtPassPhase::Middle.order(), 1);
801        assert_eq!(RAExtPassPhase::Late.order(), 2);
802        assert_eq!(RAExtPassPhase::Finalize.order(), 3);
803        assert!(RAExtPassPhase::Early.is_early());
804        assert!(!RAExtPassPhase::Early.is_late());
805    }
806    #[test]
807    pub(super) fn test_raext_config_builder() {
808        let c = RAExtPassConfig::new("p")
809            .with_phase(RAExtPassPhase::Late)
810            .with_max_iter(50)
811            .with_debug(1);
812        assert_eq!(c.name, "p");
813        assert_eq!(c.max_iterations, 50);
814        assert!(c.is_debug_enabled());
815        assert!(c.enabled);
816        let c2 = c.disabled();
817        assert!(!c2.enabled);
818    }
819    #[test]
820    pub(super) fn test_raext_stats() {
821        let mut s = RAExtPassStats::new();
822        s.visit();
823        s.visit();
824        s.modify();
825        s.iterate();
826        assert_eq!(s.nodes_visited, 2);
827        assert_eq!(s.nodes_modified, 1);
828        assert!(s.changed);
829        assert_eq!(s.iterations, 1);
830        let e = s.efficiency();
831        assert!((e - 0.5).abs() < 1e-9);
832    }
833    #[test]
834    pub(super) fn test_raext_registry() {
835        let mut r = RAExtPassRegistry::new();
836        r.register(RAExtPassConfig::new("a").with_phase(RAExtPassPhase::Early));
837        r.register(RAExtPassConfig::new("b").disabled());
838        assert_eq!(r.len(), 2);
839        assert_eq!(r.enabled_passes().len(), 1);
840        assert_eq!(r.passes_in_phase(&RAExtPassPhase::Early).len(), 1);
841    }
842    #[test]
843    pub(super) fn test_raext_cache() {
844        let mut c = RAExtCache::new(4);
845        assert!(c.get(99).is_none());
846        c.put(99, vec![1, 2, 3]);
847        let v = c.get(99).expect("v should be present in map");
848        assert_eq!(v, &[1u8, 2, 3]);
849        assert!(c.hit_rate() > 0.0);
850        assert_eq!(c.live_count(), 1);
851    }
852    #[test]
853    pub(super) fn test_raext_worklist() {
854        let mut w = RAExtWorklist::new(10);
855        w.push(5);
856        w.push(3);
857        w.push(5);
858        assert_eq!(w.len(), 2);
859        assert!(w.contains(5));
860        let first = w.pop().expect("first should be available to pop");
861        assert!(!w.contains(first));
862    }
863    #[test]
864    pub(super) fn test_raext_dom_tree() {
865        let mut dt = RAExtDomTree::new(5);
866        dt.set_idom(1, 0);
867        dt.set_idom(2, 0);
868        dt.set_idom(3, 1);
869        dt.set_idom(4, 1);
870        assert!(dt.dominates(0, 3));
871        assert!(dt.dominates(1, 4));
872        assert!(!dt.dominates(2, 3));
873        assert_eq!(dt.depth_of(3), 2);
874    }
875    #[test]
876    pub(super) fn test_raext_liveness() {
877        let mut lv = RAExtLiveness::new(3);
878        lv.add_def(0, 1);
879        lv.add_use(1, 1);
880        assert!(lv.var_is_def_in_block(0, 1));
881        assert!(lv.var_is_used_in_block(1, 1));
882        assert!(!lv.var_is_def_in_block(1, 1));
883    }
884    #[test]
885    pub(super) fn test_raext_const_folder() {
886        let mut cf = RAExtConstFolder::new();
887        assert_eq!(cf.add_i64(3, 4), Some(7));
888        assert_eq!(cf.div_i64(10, 0), None);
889        assert_eq!(cf.mul_i64(6, 7), Some(42));
890        assert_eq!(cf.and_i64(0b1100, 0b1010), 0b1000);
891        assert_eq!(cf.fold_count(), 3);
892        assert_eq!(cf.failure_count(), 1);
893    }
894    #[test]
895    pub(super) fn test_raext_dep_graph() {
896        let mut g = RAExtDepGraph::new(4);
897        g.add_edge(0, 1);
898        g.add_edge(1, 2);
899        g.add_edge(2, 3);
900        assert!(!g.has_cycle());
901        assert_eq!(g.topo_sort(), Some(vec![0, 1, 2, 3]));
902        assert_eq!(g.reachable(0).len(), 4);
903        let sccs = g.scc();
904        assert_eq!(sccs.len(), 4);
905    }
906}
oxilean_codegen/opt_regalloc/functions.rs

oxilean_codegen/opt_regalloc/
functions.rs
