oxilean_codegen/opt_alias/
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    AliasAnalysisLevel, AliasConfigExt, AliasFeatureFlags, AliasPass, AliasReport, AliasResult,
10    AliasResultExt, AliasSet, AliasStatsExt, AliasVersionInfo, AndersenSolver, LoadStoreForwarder,
11    MemoryAccessInfo, PointsToGraph, PointsToNode,
12};
13
14/// Returns `true` if two LCNF types are known to be non-aliasing.
15///
16/// In a type-safe language like Lean, values of different unrelated types
17/// cannot alias (unless they are both `Object` or erased).
18pub fn tbaa_no_alias(ty_a: &LcnfType, ty_b: &LcnfType) -> bool {
19    match (ty_a, ty_b) {
20        (a, b) if a == b => false,
21        (LcnfType::Erased, _) | (_, LcnfType::Erased) => false,
22        (LcnfType::Object, _) | (_, LcnfType::Object) => false,
23        (LcnfType::Irrelevant, _) | (_, LcnfType::Irrelevant) => false,
24        (LcnfType::Nat, LcnfType::LcnfString) | (LcnfType::LcnfString, LcnfType::Nat) => true,
25        (LcnfType::Ctor(a, _), LcnfType::Ctor(b, _)) if a != b => true,
26        (LcnfType::Fun(_, _), LcnfType::Nat) | (LcnfType::Nat, LcnfType::Fun(_, _)) => true,
27        (LcnfType::Fun(_, _), LcnfType::LcnfString)
28        | (LcnfType::LcnfString, LcnfType::Fun(_, _)) => true,
29        _ => false,
30    }
31}
32/// Recursively apply load-store forwarding to an expression.
33pub(super) fn apply_forwarding_to_expr(expr: &mut LcnfExpr, fwd: &mut LoadStoreForwarder) {
34    match expr {
35        LcnfExpr::Let { value, body, .. } => {
36            if let LcnfLetValue::App(_, _) = value {
37                fwd.clear();
38            }
39            apply_forwarding_to_expr(body, fwd);
40        }
41        LcnfExpr::Case { alts, default, .. } => {
42            let snap = fwd.store_cache.clone();
43            for alt in alts.iter_mut() {
44                fwd.store_cache = snap.clone();
45                apply_forwarding_to_expr(&mut alt.body, fwd);
46            }
47            if let Some(def) = default {
48                fwd.store_cache = snap;
49                apply_forwarding_to_expr(def, fwd);
50            }
51        }
52        LcnfExpr::Return(_) | LcnfExpr::TailCall(_, _) | LcnfExpr::Unreachable => {}
53    }
54}
55/// Compute the transitive closure of the copy edges in the points-to graph.
56#[allow(clippy::too_many_arguments)]
57pub fn transitive_pts_closure(graph: &mut PointsToGraph) {
58    let vars: Vec<LcnfVarId> = graph.nodes.keys().copied().collect();
59    let mut worklist: VecDeque<LcnfVarId> = vars.into_iter().collect();
60    while let Some(v) = worklist.pop_front() {
61        let pts: Vec<LcnfVarId> = graph.pts_of(v).clone().into_iter().collect();
62        for tgt in pts {
63            let pts_tgt: HashSet<LcnfVarId> = graph.pts_of(tgt).clone();
64            let pts_v = graph.pts.entry(v).or_default();
65            let old_len = pts_v.len();
66            pts_v.extend(pts_tgt);
67            if pts_v.len() != old_len {
68                worklist.push_back(v);
69            }
70        }
71    }
72}
73#[cfg(test)]
74mod tests {
75    use super::*;
76    use crate::lcnf::{LcnfExpr, LcnfFunDecl, LcnfLetValue, LcnfParam, LcnfType, LcnfVarId};
77    pub(super) fn v(n: u64) -> LcnfVarId {
78        LcnfVarId(n)
79    }
80    pub(super) fn make_decl(name: &str, body: LcnfExpr) -> LcnfFunDecl {
81        LcnfFunDecl {
82            name: name.to_string(),
83            original_name: None,
84            params: vec![],
85            ret_type: LcnfType::Nat,
86            body,
87            is_recursive: false,
88            is_lifted: false,
89            inline_cost: 1,
90        }
91    }
92    pub(super) fn make_param(n: u64, name: &str) -> LcnfParam {
93        LcnfParam {
94            id: v(n),
95            name: name.to_string(),
96            ty: LcnfType::Nat,
97            erased: false,
98            borrowed: false,
99        }
100    }
101    pub(super) fn ret_var(n: u64) -> LcnfExpr {
102        LcnfExpr::Return(LcnfArg::Var(v(n)))
103    }
104    #[test]
105    pub(super) fn test_alias_result_may_alias_must() {
106        assert!(AliasResult::MustAlias.may_alias());
107    }
108    #[test]
109    pub(super) fn test_alias_result_may_alias_may() {
110        assert!(AliasResult::MayAlias.may_alias());
111    }
112    #[test]
113    pub(super) fn test_alias_result_may_alias_no() {
114        assert!(!AliasResult::NoAlias.may_alias());
115    }
116    #[test]
117    pub(super) fn test_alias_result_must_alias() {
118        assert!(AliasResult::MustAlias.must_alias());
119        assert!(!AliasResult::MayAlias.must_alias());
120    }
121    #[test]
122    pub(super) fn test_alias_result_no_alias() {
123        assert!(AliasResult::NoAlias.no_alias());
124        assert!(!AliasResult::MustAlias.no_alias());
125    }
126    #[test]
127    pub(super) fn test_alias_result_merge() {
128        assert_eq!(
129            AliasResult::MustAlias.merge(AliasResult::MustAlias),
130            AliasResult::MustAlias
131        );
132        assert_eq!(
133            AliasResult::NoAlias.merge(AliasResult::NoAlias),
134            AliasResult::NoAlias
135        );
136        assert_eq!(
137            AliasResult::MustAlias.merge(AliasResult::NoAlias),
138            AliasResult::MayAlias
139        );
140    }
141    #[test]
142    pub(super) fn test_alias_set_singleton() {
143        let s = AliasSet::singleton(v(1));
144        assert!(s.contains(v(1)));
145        assert_eq!(s.len(), 1);
146        assert_eq!(s.representative, Some(v(1)));
147    }
148    #[test]
149    pub(super) fn test_alias_set_insert() {
150        let mut s = AliasSet::new();
151        s.insert(v(1));
152        s.insert(v(2));
153        assert!(s.contains(v(1)));
154        assert!(s.contains(v(2)));
155        assert_eq!(s.len(), 2);
156    }
157    #[test]
158    pub(super) fn test_alias_set_merge() {
159        let mut a = AliasSet::singleton(v(1));
160        let b = AliasSet::singleton(v(2));
161        a.merge_with(&b);
162        assert!(a.contains(v(1)));
163        assert!(a.contains(v(2)));
164    }
165    #[test]
166    pub(super) fn test_points_to_node_local() {
167        let n = PointsToNode::local(v(5), "x");
168        assert!(n.is_local());
169        assert!(!n.is_heap());
170    }
171    #[test]
172    pub(super) fn test_points_to_node_heap() {
173        let n = PointsToNode::heap(v(7), "alloc");
174        assert!(n.is_heap());
175        assert!(!n.is_local());
176    }
177    #[test]
178    pub(super) fn test_points_to_graph_add_pts() {
179        let mut g = PointsToGraph::new();
180        g.add_node(PointsToNode::local(v(1), "a"));
181        g.add_node(PointsToNode::heap(v(2), "b"));
182        g.add_pts(v(1), v(2));
183        assert!(g.pts_of(v(1)).contains(&v(2)));
184    }
185    #[test]
186    pub(super) fn test_points_to_graph_intersects() {
187        let mut g = PointsToGraph::new();
188        g.add_pts(v(1), v(3));
189        g.add_pts(v(2), v(3));
190        assert!(g.intersects(v(1), v(2)));
191    }
192    #[test]
193    pub(super) fn test_points_to_graph_no_intersect() {
194        let mut g = PointsToGraph::new();
195        g.add_pts(v(1), v(3));
196        g.add_pts(v(2), v(4));
197        assert!(!g.intersects(v(1), v(2)));
198    }
199    #[test]
200    pub(super) fn test_andersen_address_of() {
201        let mut solver = AndersenSolver::new();
202        solver.register_var(PointsToNode::local(v(1), "x"));
203        solver.register_var(PointsToNode::heap(v(2), "alloc"));
204        solver.add_address_of(v(1), v(2));
205        solver.solve();
206        assert!(solver.graph.pts_of(v(1)).contains(&v(2)));
207    }
208    #[test]
209    pub(super) fn test_andersen_copy_propagates() {
210        let mut solver = AndersenSolver::new();
211        solver.register_var(PointsToNode::local(v(1), "x"));
212        solver.register_var(PointsToNode::local(v(2), "y"));
213        solver.register_var(PointsToNode::heap(v(3), "alloc"));
214        solver.add_address_of(v(1), v(3));
215        solver.add_copy(v(2), v(1));
216        solver.solve();
217        assert!(solver.graph.pts_of(v(2)).contains(&v(3)));
218    }
219    #[test]
220    pub(super) fn test_andersen_same_var_must_alias() {
221        let mut solver = AndersenSolver::new();
222        solver.register_var(PointsToNode::local(v(1), "x"));
223        solver.add_address_of(v(1), v(1));
224        solver.solve();
225        assert_eq!(solver.query(v(1), v(1)), AliasResult::MustAlias);
226    }
227    #[test]
228    pub(super) fn test_andersen_distinct_allocs_no_alias() {
229        let mut solver = AndersenSolver::new();
230        solver.register_var(PointsToNode::local(v(1), "x"));
231        solver.register_var(PointsToNode::local(v(2), "y"));
232        solver.add_address_of(v(1), v(1));
233        solver.add_address_of(v(2), v(2));
234        solver.solve();
235        assert_eq!(solver.query(v(1), v(2)), AliasResult::NoAlias);
236    }
237    #[test]
238    pub(super) fn test_tbaa_nat_string_no_alias() {
239        assert!(tbaa_no_alias(&LcnfType::Nat, &LcnfType::LcnfString));
240    }
241    #[test]
242    pub(super) fn test_tbaa_same_type_may_alias() {
243        assert!(!tbaa_no_alias(&LcnfType::Nat, &LcnfType::Nat));
244    }
245    #[test]
246    pub(super) fn test_tbaa_different_ctors_no_alias() {
247        assert!(tbaa_no_alias(
248            &LcnfType::Ctor("List".to_string(), vec![]),
249            &LcnfType::Ctor("Option".to_string(), vec![])
250        ));
251    }
252    #[test]
253    pub(super) fn test_tbaa_object_conservative() {
254        assert!(!tbaa_no_alias(&LcnfType::Object, &LcnfType::Nat));
255    }
256    #[test]
257    pub(super) fn test_memory_access_definitely_disjoint() {
258        let a = MemoryAccessInfo {
259            base: v(1),
260            offset: Some(0),
261            size: Some(4),
262            is_volatile: false,
263            access_type: LcnfType::Nat,
264            is_write: false,
265        };
266        let b = MemoryAccessInfo {
267            base: v(1),
268            offset: Some(8),
269            size: Some(4),
270            is_volatile: false,
271            access_type: LcnfType::Nat,
272            is_write: false,
273        };
274        assert!(a.definitely_disjoint(&b));
275    }
276    #[test]
277    pub(super) fn test_memory_access_overlapping() {
278        let a = MemoryAccessInfo {
279            base: v(1),
280            offset: Some(0),
281            size: Some(8),
282            is_volatile: false,
283            access_type: LcnfType::Nat,
284            is_write: false,
285        };
286        let b = MemoryAccessInfo {
287            base: v(1),
288            offset: Some(4),
289            size: Some(4),
290            is_volatile: false,
291            access_type: LcnfType::Nat,
292            is_write: false,
293        };
294        assert!(!a.definitely_disjoint(&b));
295    }
296    #[test]
297    pub(super) fn test_alias_pass_basic_aa_same_var() {
298        let mut pass = AliasPass::with_level(AliasAnalysisLevel::BasicAA);
299        let mut decls = vec![];
300        pass.run(&mut decls);
301        assert_eq!(pass.query(v(1), v(1)), AliasResult::MustAlias);
302    }
303    #[test]
304    pub(super) fn test_alias_pass_basic_aa_diff_var() {
305        let mut pass = AliasPass::with_level(AliasAnalysisLevel::BasicAA);
306        let mut decls = vec![];
307        pass.run(&mut decls);
308        assert_eq!(pass.query(v(1), v(2)), AliasResult::MayAlias);
309    }
310    #[test]
311    pub(super) fn test_alias_pass_no_alias_level() {
312        let mut pass = AliasPass::with_level(AliasAnalysisLevel::NoAlias);
313        let mut decls = vec![];
314        pass.run(&mut decls);
315        assert_eq!(pass.query(v(1), v(1)), AliasResult::MayAlias);
316    }
317    #[test]
318    pub(super) fn test_alias_pass_report_counters() {
319        let mut pass = AliasPass::with_level(AliasAnalysisLevel::BasicAA);
320        let mut decls = vec![];
321        pass.run(&mut decls);
322        pass.query(v(1), v(1));
323        pass.query(v(1), v(2));
324        let r = pass.report();
325        assert_eq!(r.must_alias, 1);
326        assert_eq!(r.may_alias, 1);
327        assert_eq!(r.pairs_analyzed, 2);
328    }
329    #[test]
330    pub(super) fn test_alias_pass_run_with_decls() {
331        let body = LcnfExpr::Let {
332            id: v(10),
333            name: "x".to_string(),
334            ty: LcnfType::Nat,
335            value: LcnfLetValue::Ctor("Nat.zero".to_string(), 0, vec![]),
336            body: Box::new(ret_var(10)),
337        };
338        let decl = make_decl("test_fn", body);
339        let mut decls = vec![decl];
340        let mut pass = AliasPass::new();
341        pass.run(&mut decls);
342        assert_eq!(pass.query(v(10), v(10)), AliasResult::MustAlias);
343    }
344    #[test]
345    pub(super) fn test_alias_pass_tbaa_no_alias() {
346        let mut pass = AliasPass::with_level(AliasAnalysisLevel::TypeBasedAA);
347        pass.type_map.insert(v(1), LcnfType::Nat);
348        pass.type_map.insert(v(2), LcnfType::LcnfString);
349        let mut decls = vec![];
350        pass.run(&mut decls);
351        assert_eq!(pass.query(v(1), v(2)), AliasResult::NoAlias);
352    }
353    #[test]
354    pub(super) fn test_alias_pass_cfl_with_params() {
355        let body = ret_var(0);
356        let mut decl = make_decl("f", body);
357        decl.params = vec![make_param(0, "n"), make_param(1, "m")];
358        let mut decls = vec![decl];
359        let mut pass = AliasPass::new();
360        pass.run(&mut decls);
361        let r = pass.query(v(0), v(1));
362        assert!(matches!(r, AliasResult::NoAlias | AliasResult::MayAlias));
363    }
364    #[test]
365    pub(super) fn test_alias_report_no_alias_ratio() {
366        let mut r = AliasReport::default();
367        r.pairs_analyzed = 10;
368        r.no_alias = 7;
369        assert!((r.no_alias_ratio() - 0.7).abs() < 1e-6);
370    }
371    #[test]
372    pub(super) fn test_alias_report_empty() {
373        let r = AliasReport::default();
374        assert_eq!(r.no_alias_ratio(), 0.0);
375    }
376    #[test]
377    pub(super) fn test_load_store_forwarder_basic() {
378        let mut fwd = LoadStoreForwarder::new();
379        fwd.record_store(v(1), Some(0), v(5));
380        assert_eq!(fwd.forward_load(v(1), Some(0)), Some(v(5)));
381    }
382    #[test]
383    pub(super) fn test_load_store_forwarder_miss() {
384        let fwd = LoadStoreForwarder::new();
385        assert_eq!(fwd.forward_load(v(1), Some(0)), None);
386    }
387    #[test]
388    pub(super) fn test_load_store_forwarder_invalidate() {
389        let mut fwd = LoadStoreForwarder::new();
390        fwd.record_store(v(1), Some(0), v(5));
391        fwd.invalidate(v(1));
392        assert_eq!(fwd.forward_load(v(1), Some(0)), None);
393    }
394    #[test]
395    pub(super) fn test_alias_analysis_level_description() {
396        assert!(!AliasAnalysisLevel::CFLAndersen.description().is_empty());
397        assert!(!AliasAnalysisLevel::NoAlias.description().is_empty());
398    }
399    #[test]
400    pub(super) fn test_alias_analysis_level_uses_points_to() {
401        assert!(AliasAnalysisLevel::CFLAndersen.uses_points_to());
402        assert!(AliasAnalysisLevel::CFLSteensgaard.uses_points_to());
403        assert!(!AliasAnalysisLevel::BasicAA.uses_points_to());
404        assert!(!AliasAnalysisLevel::TypeBasedAA.uses_points_to());
405    }
406}
407/// Alias analysis diagnostic helper
408#[allow(dead_code)]
409pub fn alias_result_str(r: &AliasResultExt) -> &'static str {
410    match r {
411        AliasResultExt::NoAlias => "NoAlias",
412        AliasResultExt::MayAlias => "MayAlias",
413        AliasResultExt::PartialAlias => "PartialAlias",
414        AliasResultExt::MustAlias => "MustAlias",
415    }
416}
417/// Alias analysis is_must_alias shorthand
418#[allow(dead_code)]
419pub fn alias_is_must(r: &AliasResultExt) -> bool {
420    *r == AliasResultExt::MustAlias
421}
422/// Alias analysis is_no_alias shorthand
423#[allow(dead_code)]
424pub fn alias_is_no(r: &AliasResultExt) -> bool {
425    *r == AliasResultExt::NoAlias
426}
427/// Alias analysis version info default
428#[allow(dead_code)]
429pub fn alias_default_version() -> AliasVersionInfo {
430    AliasVersionInfo::default()
431}
432/// Alias analysis final code stats helper
433#[allow(dead_code)]
434pub fn alias_stats_summary(stats: &AliasStatsExt) -> String {
435    format!(
436        "queries={}, must={:.1}%, no={:.1}%",
437        stats.queries_total,
438        if stats.queries_total > 0 {
439            stats.must_alias_count as f64 / stats.queries_total as f64 * 100.0
440        } else {
441            0.0
442        },
443        if stats.queries_total > 0 {
444            stats.no_alias_count as f64 / stats.queries_total as f64 * 100.0
445        } else {
446            0.0
447        },
448    )
449}
450/// Default alias feature flags
451#[allow(dead_code)]
452pub fn alias_default_features() -> AliasFeatureFlags {
453    AliasFeatureFlags {
454        enable_tbaa: true,
455        enable_field_sensitivity: false,
456        enable_flow_sensitivity: false,
457        enable_context_sensitivity: false,
458        enable_escape_analysis: true,
459        enable_cfl_reachability: false,
460    }
461}
462/// Alias analysis config from feature flags
463#[allow(dead_code)]
464pub fn alias_config_from_features(flags: &AliasFeatureFlags) -> AliasConfigExt {
465    AliasConfigExt {
466        enable_field_sensitivity: flags.enable_field_sensitivity,
467        enable_flow_sensitivity: flags.enable_flow_sensitivity,
468        enable_context_sensitivity: flags.enable_context_sensitivity,
469        track_heap: flags.enable_escape_analysis,
470        ..Default::default()
471    }
472}
473/// Print alias config summary
474#[allow(dead_code)]
475pub fn alias_config_summary(cfg: &AliasConfigExt) -> String {
476    format!(
477        "AliasConfig {{ level={}, field={}, flow={}, ctx={} }}",
478        cfg.level,
479        cfg.enable_field_sensitivity,
480        cfg.enable_flow_sensitivity,
481        cfg.enable_context_sensitivity
482    )
483}
484/// Alias analysis version string
485#[allow(dead_code)]
486pub const ALIAS_PASS_VERSION: &str = "2.0.0";
487/// Alias default max iterations
488#[allow(dead_code)]
489pub const ALIAS_MAX_ITERS: usize = 100;
490/// Andersen pass name
491#[allow(dead_code)]
492pub const ANDERSEN_PASS: &str = "andersen-points-to";
493/// Steensgaard pass name
494#[allow(dead_code)]
495pub const STEENSGAARD_PASS: &str = "steensgaard-points-to";
496/// CFL-Andersen pass name
497#[allow(dead_code)]
498pub const CFL_ANDERSEN_PASS: &str = "cfl-andersen-points-to";
499/// Alias analysis pass name constants
500#[allow(dead_code)]
501pub const ALIAS_PASS_NAME_BASIC: &str = "basic-aa";
502#[allow(dead_code)]
503pub const ALIAS_PASS_NAME_TBAA: &str = "type-based-aa";
504#[allow(dead_code)]
505pub const ALIAS_PASS_NAME_SCOPED: &str = "scoped-noalias";
506#[allow(dead_code)]
507pub const ALIAS_PASS_NAME_GLOBALS: &str = "globals-aa";
508#[allow(dead_code)]
509pub const ALIAS_PASS_NAME_CFL: &str = "cfl-steensgaard-aa";
510/// Default alias pass for oxilean
511#[allow(dead_code)]
512pub const OXILEAN_DEFAULT_ALIAS_PASS: &str = "andersen-points-to";
513/// Alias analysis pipeline default passes
514#[allow(dead_code)]
515pub fn alias_default_pipeline_passes() -> Vec<&'static str> {
516    vec![
517        ALIAS_PASS_NAME_BASIC,
518        ALIAS_PASS_NAME_TBAA,
519        ALIAS_PASS_NAME_GLOBALS,
520    ]
521}
522/// Alias analysis result ordering (most certain first)
523#[allow(dead_code)]
524pub fn alias_certainty_order(r: &AliasResultExt) -> u32 {
525    match r {
526        AliasResultExt::MustAlias => 3,
527        AliasResultExt::NoAlias => 2,
528        AliasResultExt::PartialAlias => 1,
529        AliasResultExt::MayAlias => 0,
530    }
531}
532/// Alias version 2.0 marker constant
533#[allow(dead_code)]
534pub const ALIAS_V2: bool = true;
oxilean_codegen/opt_alias/functions.rs

oxilean_codegen/opt_alias/
functions.rs
