oxilean_codegen/native_backend/
functions.rs

1//! Auto-generated module
2//!
3//! 🤖 Generated with [SplitRS](https://github.com/cool-japan/splitrs)
4
5use crate::lcnf::*;
6use std::collections::{HashMap, HashSet};
7
8use super::types::{
9    BasicBlock, BlockId, CondCode, NatAnalysisCache, NatConstantFoldingHelper, NatDepGraph,
10    NatDominatorTree, NatLivenessInfo, NatPassConfig, NatPassPhase, NatPassRegistry, NatPassStats,
11    NatWorklist, NativeBackend, NativeEmitConfig, NativeEmitStats, NativeInst, NativeModule,
12    NativeType, NativeValue, Register, RegisterAllocator,
13};
14
15/// Map an LCNF type to a native type.
16pub(super) fn lcnf_type_to_native(ty: &LcnfType) -> NativeType {
17    match ty {
18        LcnfType::Nat => NativeType::I64,
19        LcnfType::Int => NativeType::I64,
20        LcnfType::LcnfString => NativeType::Ptr,
21        LcnfType::Object => NativeType::Ptr,
22        LcnfType::Var(_) => NativeType::Ptr,
23        LcnfType::Fun(_, _) => NativeType::Ptr,
24        LcnfType::Ctor(_, _) => NativeType::Ptr,
25        LcnfType::Erased | LcnfType::Irrelevant | LcnfType::Unit => NativeType::Void,
26    }
27}
28/// Compile an LCNF module to native IR with default settings.
29pub fn compile_to_native(module: &LcnfModule) -> NativeModule {
30    let mut backend = NativeBackend::default_backend();
31    backend.compile_module(module)
32}
33/// Compile and perform register allocation.
34pub fn compile_and_regalloc(
35    module: &LcnfModule,
36    num_regs: usize,
37) -> (NativeModule, Vec<HashMap<Register, Register>>) {
38    let mut backend = NativeBackend::default_backend();
39    let native_module = backend.compile_module(module);
40    let mut allocations = Vec::new();
41    for func in &native_module.functions {
42        let mut allocator = RegisterAllocator::new(num_regs);
43        let alloc = allocator.allocate(func);
44        allocations.push(alloc);
45    }
46    (native_module, allocations)
47}
48#[cfg(test)]
49mod tests {
50    use super::*;
51    pub(super) fn vid(n: u64) -> LcnfVarId {
52        LcnfVarId(n)
53    }
54    pub(super) fn mk_param(n: u64, name: &str) -> LcnfParam {
55        LcnfParam {
56            id: vid(n),
57            name: name.to_string(),
58            ty: LcnfType::Nat,
59            erased: false,
60            borrowed: false,
61        }
62    }
63    pub(super) fn mk_fun_decl(name: &str, body: LcnfExpr) -> LcnfFunDecl {
64        LcnfFunDecl {
65            name: name.to_string(),
66            original_name: None,
67            params: vec![mk_param(0, "n")],
68            ret_type: LcnfType::Nat,
69            body,
70            is_recursive: false,
71            is_lifted: false,
72            inline_cost: 1,
73        }
74    }
75    pub(super) fn mk_module(decls: Vec<LcnfFunDecl>) -> LcnfModule {
76        LcnfModule {
77            fun_decls: decls,
78            extern_decls: vec![],
79            name: "test_mod".to_string(),
80            metadata: LcnfModuleMetadata::default(),
81        }
82    }
83    #[test]
84    pub(super) fn test_native_type_size() {
85        assert_eq!(NativeType::I8.size_bytes(), 1);
86        assert_eq!(NativeType::I16.size_bytes(), 2);
87        assert_eq!(NativeType::I32.size_bytes(), 4);
88        assert_eq!(NativeType::I64.size_bytes(), 8);
89        assert_eq!(NativeType::Ptr.size_bytes(), 8);
90        assert_eq!(NativeType::Void.size_bytes(), 0);
91    }
92    #[test]
93    pub(super) fn test_native_type_display() {
94        assert_eq!(NativeType::I64.to_string(), "i64");
95        assert_eq!(NativeType::Ptr.to_string(), "ptr");
96        assert_eq!(NativeType::Void.to_string(), "void");
97    }
98    #[test]
99    pub(super) fn test_native_type_properties() {
100        assert!(NativeType::I32.is_integer());
101        assert!(!NativeType::I32.is_float());
102        assert!(NativeType::F64.is_float());
103        assert!(NativeType::Ptr.is_pointer());
104    }
105    #[test]
106    pub(super) fn test_register_virtual_physical() {
107        let vr = Register::virt(5);
108        assert!(vr.is_virtual());
109        assert!(!vr.is_physical());
110        let pr = Register::phys(3);
111        assert!(!pr.is_virtual());
112        assert!(pr.is_physical());
113    }
114    #[test]
115    pub(super) fn test_register_display() {
116        assert_eq!(Register::virt(5).to_string(), "v5");
117        assert_eq!(Register::phys(3).to_string(), "r3");
118    }
119    #[test]
120    pub(super) fn test_native_value_display() {
121        assert_eq!(NativeValue::Reg(Register::virt(0)).to_string(), "v0");
122        assert_eq!(NativeValue::Imm(42).to_string(), "#42");
123        assert_eq!(NativeValue::FRef("foo".to_string()).to_string(), "@foo");
124        assert_eq!(NativeValue::StackSlot(3).to_string(), "ss3");
125    }
126    #[test]
127    pub(super) fn test_block_id_display() {
128        assert_eq!(BlockId(0).to_string(), "bb0");
129        assert_eq!(BlockId(5).to_string(), "bb5");
130    }
131    #[test]
132    pub(super) fn test_basic_block_successors() {
133        let mut block = BasicBlock::new(BlockId(0));
134        block.push_inst(NativeInst::Br { target: BlockId(1) });
135        assert_eq!(block.successors(), vec![BlockId(1)]);
136        let mut block2 = BasicBlock::new(BlockId(1));
137        block2.push_inst(NativeInst::CondBr {
138            cond: NativeValue::Reg(Register::virt(0)),
139            then_target: BlockId(2),
140            else_target: BlockId(3),
141        });
142        assert_eq!(block2.successors(), vec![BlockId(2), BlockId(3)]);
143    }
144    #[test]
145    pub(super) fn test_inst_is_terminator() {
146        assert!(NativeInst::Br { target: BlockId(0) }.is_terminator());
147        assert!(NativeInst::Ret { value: None }.is_terminator());
148        assert!(!NativeInst::Nop.is_terminator());
149        assert!(!NativeInst::LoadImm {
150            dst: Register::virt(0),
151            ty: NativeType::I64,
152            value: 0
153        }
154        .is_terminator());
155    }
156    #[test]
157    pub(super) fn test_inst_dst_reg() {
158        let inst = NativeInst::Add {
159            dst: Register::virt(5),
160            ty: NativeType::I64,
161            lhs: NativeValue::Reg(Register::virt(0)),
162            rhs: NativeValue::Imm(1),
163        };
164        assert_eq!(inst.dst_reg(), Some(Register::virt(5)));
165        let inst2 = NativeInst::Ret { value: None };
166        assert_eq!(inst2.dst_reg(), None);
167    }
168    #[test]
169    pub(super) fn test_inst_src_regs() {
170        let inst = NativeInst::Add {
171            dst: Register::virt(5),
172            ty: NativeType::I64,
173            lhs: NativeValue::Reg(Register::virt(1)),
174            rhs: NativeValue::Reg(Register::virt(2)),
175        };
176        let srcs = inst.src_regs();
177        assert_eq!(srcs.len(), 2);
178        assert!(srcs.contains(&Register::virt(1)));
179        assert!(srcs.contains(&Register::virt(2)));
180    }
181    #[test]
182    pub(super) fn test_compile_simple_function() {
183        let body = LcnfExpr::Return(LcnfArg::Var(vid(0)));
184        let decl = mk_fun_decl("identity", body);
185        let module = mk_module(vec![decl]);
186        let mut backend = NativeBackend::default_backend();
187        let native_module = backend.compile_module(&module);
188        assert_eq!(native_module.functions.len(), 1);
189        let func = &native_module.functions[0];
190        assert_eq!(func.name, "identity");
191        assert!(!func.blocks.is_empty());
192    }
193    #[test]
194    pub(super) fn test_compile_case_expression() {
195        let body = LcnfExpr::Case {
196            scrutinee: vid(0),
197            scrutinee_ty: LcnfType::Ctor("Bool".into(), vec![]),
198            alts: vec![
199                LcnfAlt {
200                    ctor_name: "False".into(),
201                    ctor_tag: 0,
202                    params: vec![],
203                    body: LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(0))),
204                },
205                LcnfAlt {
206                    ctor_name: "True".into(),
207                    ctor_tag: 1,
208                    params: vec![],
209                    body: LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(1))),
210                },
211            ],
212            default: Some(Box::new(LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(99))))),
213        };
214        let decl = mk_fun_decl("to_nat", body);
215        let module = mk_module(vec![decl]);
216        let mut backend = NativeBackend::default_backend();
217        let native_module = backend.compile_module(&module);
218        let func = &native_module.functions[0];
219        assert!(func.blocks.len() > 1);
220    }
221    #[test]
222    pub(super) fn test_register_allocation() {
223        let body = LcnfExpr::Let {
224            id: vid(1),
225            name: "a".to_string(),
226            ty: LcnfType::Nat,
227            value: LcnfLetValue::Lit(LcnfLit::Nat(42)),
228            body: Box::new(LcnfExpr::Let {
229                id: vid(2),
230                name: "b".to_string(),
231                ty: LcnfType::Nat,
232                value: LcnfLetValue::Lit(LcnfLit::Nat(10)),
233                body: Box::new(LcnfExpr::Return(LcnfArg::Var(vid(1)))),
234            }),
235        };
236        let decl = mk_fun_decl("test_alloc", body);
237        let module = mk_module(vec![decl]);
238        let (native_module, allocations) = compile_and_regalloc(&module, 8);
239        assert_eq!(native_module.functions.len(), 1);
240        assert_eq!(allocations.len(), 1);
241        let alloc = &allocations[0];
242        for (vreg, phys) in alloc {
243            assert!(vreg.is_virtual());
244            assert!(phys.is_physical());
245        }
246    }
247    #[test]
248    pub(super) fn test_native_module_display() {
249        let module = NativeModule::new("test");
250        let s = module.to_string();
251        assert!(s.contains("module: test"));
252    }
253    #[test]
254    pub(super) fn test_native_emit_config_default() {
255        let cfg = NativeEmitConfig::default();
256        assert_eq!(cfg.opt_level, 1);
257        assert!(!cfg.debug_info);
258        assert_eq!(cfg.target_arch, "x86_64");
259    }
260    #[test]
261    pub(super) fn test_native_emit_stats_display() {
262        let stats = NativeEmitStats {
263            functions_compiled: 3,
264            blocks_generated: 10,
265            ..Default::default()
266        };
267        let s = stats.to_string();
268        assert!(s.contains("fns=3"));
269        assert!(s.contains("blocks=10"));
270    }
271    #[test]
272    pub(super) fn test_lcnf_type_to_native() {
273        assert_eq!(lcnf_type_to_native(&LcnfType::Nat), NativeType::I64);
274        assert_eq!(lcnf_type_to_native(&LcnfType::Object), NativeType::Ptr);
275        assert_eq!(lcnf_type_to_native(&LcnfType::Unit), NativeType::Void);
276    }
277    #[test]
278    pub(super) fn test_compile_let_chain() {
279        let body = LcnfExpr::Let {
280            id: vid(1),
281            name: "a".to_string(),
282            ty: LcnfType::Nat,
283            value: LcnfLetValue::Lit(LcnfLit::Nat(42)),
284            body: Box::new(LcnfExpr::Let {
285                id: vid(2),
286                name: "b".to_string(),
287                ty: LcnfType::Nat,
288                value: LcnfLetValue::App(LcnfArg::Var(vid(99)), vec![LcnfArg::Var(vid(1))]),
289                body: Box::new(LcnfExpr::Return(LcnfArg::Var(vid(2)))),
290            }),
291        };
292        let decl = mk_fun_decl("chain", body);
293        let mut backend = NativeBackend::default_backend();
294        let func = backend.compile_fun_decl(&decl);
295        assert!(!func.blocks.is_empty());
296        assert!(func.instruction_count() > 0);
297    }
298    #[test]
299    pub(super) fn test_virtual_registers() {
300        let body = LcnfExpr::Let {
301            id: vid(1),
302            name: "a".to_string(),
303            ty: LcnfType::Nat,
304            value: LcnfLetValue::Lit(LcnfLit::Nat(1)),
305            body: Box::new(LcnfExpr::Return(LcnfArg::Var(vid(1)))),
306        };
307        let decl = mk_fun_decl("test", body);
308        let mut backend = NativeBackend::default_backend();
309        let func = backend.compile_fun_decl(&decl);
310        let vregs = func.virtual_registers();
311        assert!(!vregs.is_empty());
312    }
313    #[test]
314    pub(super) fn test_cond_code_display() {
315        assert_eq!(CondCode::Eq.to_string(), "eq");
316        assert_eq!(CondCode::Lt.to_string(), "lt");
317        assert_eq!(CondCode::Uge.to_string(), "uge");
318    }
319    #[test]
320    pub(super) fn test_native_func_display() {
321        let body = LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(0)));
322        let decl = mk_fun_decl("display_test", body);
323        let mut backend = NativeBackend::default_backend();
324        let func = backend.compile_fun_decl(&decl);
325        let s = func.to_string();
326        assert!(s.contains("func @display_test"));
327    }
328}
329#[cfg(test)]
330mod Nat_infra_tests {
331    use super::*;
332    #[test]
333    pub(super) fn test_pass_config() {
334        let config = NatPassConfig::new("test_pass", NatPassPhase::Transformation);
335        assert!(config.enabled);
336        assert!(config.phase.is_modifying());
337        assert_eq!(config.phase.name(), "transformation");
338    }
339    #[test]
340    pub(super) fn test_pass_stats() {
341        let mut stats = NatPassStats::new();
342        stats.record_run(10, 100, 3);
343        stats.record_run(20, 200, 5);
344        assert_eq!(stats.total_runs, 2);
345        assert!((stats.average_changes_per_run() - 15.0).abs() < 0.01);
346        assert!((stats.success_rate() - 1.0).abs() < 0.01);
347        let s = stats.format_summary();
348        assert!(s.contains("Runs: 2/2"));
349    }
350    #[test]
351    pub(super) fn test_pass_registry() {
352        let mut reg = NatPassRegistry::new();
353        reg.register(NatPassConfig::new("pass_a", NatPassPhase::Analysis));
354        reg.register(NatPassConfig::new("pass_b", NatPassPhase::Transformation).disabled());
355        assert_eq!(reg.total_passes(), 2);
356        assert_eq!(reg.enabled_count(), 1);
357        reg.update_stats("pass_a", 5, 50, 2);
358        let stats = reg.get_stats("pass_a").expect("stats should exist");
359        assert_eq!(stats.total_changes, 5);
360    }
361    #[test]
362    pub(super) fn test_analysis_cache() {
363        let mut cache = NatAnalysisCache::new(10);
364        cache.insert("key1".to_string(), vec![1, 2, 3]);
365        assert!(cache.get("key1").is_some());
366        assert!(cache.get("key2").is_none());
367        assert!((cache.hit_rate() - 0.5).abs() < 0.01);
368        cache.invalidate("key1");
369        assert!(!cache.entries["key1"].valid);
370        assert_eq!(cache.size(), 1);
371    }
372    #[test]
373    pub(super) fn test_worklist() {
374        let mut wl = NatWorklist::new();
375        assert!(wl.push(1));
376        assert!(wl.push(2));
377        assert!(!wl.push(1));
378        assert_eq!(wl.len(), 2);
379        assert_eq!(wl.pop(), Some(1));
380        assert!(!wl.contains(1));
381        assert!(wl.contains(2));
382    }
383    #[test]
384    pub(super) fn test_dominator_tree() {
385        let mut dt = NatDominatorTree::new(5);
386        dt.set_idom(1, 0);
387        dt.set_idom(2, 0);
388        dt.set_idom(3, 1);
389        assert!(dt.dominates(0, 3));
390        assert!(dt.dominates(1, 3));
391        assert!(!dt.dominates(2, 3));
392        assert!(dt.dominates(3, 3));
393    }
394    #[test]
395    pub(super) fn test_liveness() {
396        let mut liveness = NatLivenessInfo::new(3);
397        liveness.add_def(0, 1);
398        liveness.add_use(1, 1);
399        assert!(liveness.defs[0].contains(&1));
400        assert!(liveness.uses[1].contains(&1));
401    }
402    #[test]
403    pub(super) fn test_constant_folding() {
404        assert_eq!(NatConstantFoldingHelper::fold_add_i64(3, 4), Some(7));
405        assert_eq!(NatConstantFoldingHelper::fold_div_i64(10, 0), None);
406        assert_eq!(NatConstantFoldingHelper::fold_div_i64(10, 2), Some(5));
407        assert_eq!(
408            NatConstantFoldingHelper::fold_bitand_i64(0b1100, 0b1010),
409            0b1000
410        );
411        assert_eq!(NatConstantFoldingHelper::fold_bitnot_i64(0), -1);
412    }
413    #[test]
414    pub(super) fn test_dep_graph() {
415        let mut g = NatDepGraph::new();
416        g.add_dep(1, 2);
417        g.add_dep(2, 3);
418        g.add_dep(1, 3);
419        assert_eq!(g.dependencies_of(2), vec![1]);
420        let topo = g.topological_sort();
421        assert_eq!(topo.len(), 3);
422        assert!(!g.has_cycle());
423        let pos: std::collections::HashMap<u32, usize> =
424            topo.iter().enumerate().map(|(i, &n)| (n, i)).collect();
425        assert!(pos[&1] < pos[&2]);
426        assert!(pos[&1] < pos[&3]);
427        assert!(pos[&2] < pos[&3]);
428    }
429}
oxilean_codegen/native_backend/functions.rs

oxilean_codegen/native_backend/
functions.rs
