1use crate::lcnf::{
6 LcnfArg, LcnfExpr, LcnfFunDecl, LcnfLetValue, LcnfLit, LcnfParam, LcnfType, LcnfVarId,
7};
8use std::collections::HashMap;
9
10use super::types::{
11 BindingEnv, BindingTime, PEAnalysisCache, PEConstantFoldingHelper, PEDepGraph, PEDominatorTree,
12 PEExtCache, PEExtConstFolder, PEExtDepGraph, PEExtDomTree, PEExtLiveness, PEExtPassConfig,
13 PEExtPassPhase, PEExtPassRegistry, PEExtPassStats, PEExtWorklist, PELivenessInfo, PEPassConfig,
14 PEPassPhase, PEPassRegistry, PEPassStats, PEWorklist, PartialEvalConfig, PartialEvalReport,
15 PartialEvaluator, PartialValue, SpecializationKey,
16};
17
18pub fn analyze_binding_times(
21 decl: &LcnfFunDecl,
22 call_site_env: &[PartialValue],
23) -> Vec<BindingTime> {
24 decl.params
25 .iter()
26 .enumerate()
27 .map(|(i, _param)| {
28 let pv = call_site_env.get(i).unwrap_or(&PartialValue::Unknown);
29 BindingTime::from_partial(pv)
30 })
31 .collect()
32}
33#[cfg(test)]
34mod tests {
35 use super::*;
36 use crate::lcnf::{
37 LcnfAlt, LcnfArg, LcnfExpr, LcnfFunDecl, LcnfLetValue, LcnfLit, LcnfParam, LcnfType,
38 LcnfVarId,
39 };
40 pub(super) fn make_nat_lit(id: u64, n: u64, body: LcnfExpr) -> LcnfExpr {
41 LcnfExpr::Let {
42 id: LcnfVarId(id),
43 name: format!("v{}", id),
44 ty: LcnfType::Nat,
45 value: LcnfLetValue::Lit(LcnfLit::Nat(n)),
46 body: Box::new(body),
47 }
48 }
49 pub(super) fn make_return_nat(n: u64) -> LcnfExpr {
50 LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(n)))
51 }
52 pub(super) fn make_decl(name: &str, params: Vec<LcnfParam>, body: LcnfExpr) -> LcnfFunDecl {
53 LcnfFunDecl {
54 name: name.to_string(),
55 original_name: None,
56 params,
57 ret_type: LcnfType::Nat,
58 body,
59 is_recursive: false,
60 is_lifted: false,
61 inline_cost: 0,
62 }
63 }
64 pub(super) fn make_param(id: u64, name: &str) -> LcnfParam {
65 LcnfParam {
66 id: LcnfVarId(id),
67 name: name.to_string(),
68 ty: LcnfType::Nat,
69 erased: false,
70 borrowed: false,
71 }
72 }
73 #[test]
74 pub(super) fn test_partial_value_is_known() {
75 let v = PartialValue::Known(LcnfLit::Nat(42));
76 assert!(v.is_known());
77 assert!(!v.is_unknown());
78 }
79 #[test]
80 pub(super) fn test_partial_value_is_unknown() {
81 assert!(PartialValue::Unknown.is_unknown());
82 assert!(!PartialValue::Unknown.is_known());
83 }
84 #[test]
85 pub(super) fn test_partial_value_as_lit() {
86 let v = PartialValue::Known(LcnfLit::Nat(7));
87 assert_eq!(v.as_lit(), Some(&LcnfLit::Nat(7)));
88 assert_eq!(PartialValue::Unknown.as_lit(), None);
89 }
90 #[test]
91 pub(super) fn test_partial_value_meet_same_known() {
92 let a = PartialValue::Known(LcnfLit::Nat(3));
93 let b = PartialValue::Known(LcnfLit::Nat(3));
94 assert_eq!(
95 PartialValue::meet(&a, &b),
96 PartialValue::Known(LcnfLit::Nat(3))
97 );
98 }
99 #[test]
100 pub(super) fn test_partial_value_meet_different_known_gives_unknown() {
101 let a = PartialValue::Known(LcnfLit::Nat(1));
102 let b = PartialValue::Known(LcnfLit::Nat(2));
103 assert_eq!(PartialValue::meet(&a, &b), PartialValue::Unknown);
104 }
105 #[test]
106 pub(super) fn test_partial_value_meet_contradiction_propagates() {
107 let a = PartialValue::Contradiction;
108 let b = PartialValue::Known(LcnfLit::Nat(1));
109 assert_eq!(PartialValue::meet(&a, &b), PartialValue::Contradiction);
110 }
111 #[test]
112 pub(super) fn test_partial_value_display() {
113 assert!(PartialValue::Unknown.display().contains("Unknown"));
114 assert!(PartialValue::Contradiction
115 .display()
116 .contains("Contradiction"));
117 }
118 #[test]
119 pub(super) fn test_binding_env_lookup_unknown_default() {
120 let env = BindingEnv::new();
121 assert_eq!(env.lookup(LcnfVarId(99)), &PartialValue::Unknown);
122 }
123 #[test]
124 pub(super) fn test_binding_env_bind_and_lookup() {
125 let mut env = BindingEnv::new();
126 env.bind(LcnfVarId(1), PartialValue::Known(LcnfLit::Nat(5)));
127 assert_eq!(
128 env.lookup(LcnfVarId(1)),
129 &PartialValue::Known(LcnfLit::Nat(5))
130 );
131 }
132 #[test]
133 pub(super) fn test_binding_env_len() {
134 let mut env = BindingEnv::new();
135 assert_eq!(env.len(), 0);
136 env.bind(LcnfVarId(0), PartialValue::Unknown);
137 assert_eq!(env.len(), 1);
138 }
139 #[test]
140 pub(super) fn test_binding_env_is_empty() {
141 let env = BindingEnv::new();
142 assert!(env.is_empty());
143 }
144 #[test]
145 pub(super) fn test_binding_env_merge_from() {
146 let mut e1 = BindingEnv::new();
147 e1.bind(LcnfVarId(0), PartialValue::Known(LcnfLit::Nat(1)));
148 let mut e2 = BindingEnv::new();
149 e2.bind(LcnfVarId(1), PartialValue::Known(LcnfLit::Nat(2)));
150 e1.merge_from(&e2);
151 assert!(e1.lookup(LcnfVarId(1)).is_known());
152 }
153 #[test]
154 pub(super) fn test_spec_key_mangled_name_with_nat() {
155 let key = SpecializationKey::new("foo", vec![PartialValue::Known(LcnfLit::Nat(42))]);
156 assert!(key.mangled_name().contains("42"));
157 assert!(key.mangled_name().starts_with("foo"));
158 }
159 #[test]
160 pub(super) fn test_spec_key_mangled_name_unknown_not_added() {
161 let key = SpecializationKey::new("bar", vec![PartialValue::Unknown]);
162 assert_eq!(key.mangled_name(), "bar");
163 }
164 #[test]
165 pub(super) fn test_spec_key_has_static_args_true() {
166 let key = SpecializationKey::new(
167 "f",
168 vec![PartialValue::Known(LcnfLit::Nat(0)), PartialValue::Unknown],
169 );
170 assert!(key.has_static_args());
171 }
172 #[test]
173 pub(super) fn test_spec_key_has_static_args_false() {
174 let key = SpecializationKey::new("f", vec![PartialValue::Unknown]);
175 assert!(!key.has_static_args());
176 }
177 #[test]
178 pub(super) fn test_default_config() {
179 let cfg = PartialEvalConfig::default();
180 assert_eq!(cfg.max_specializations, 100);
181 assert_eq!(cfg.max_depth, 50);
182 assert!(cfg.enable_memoization);
183 }
184 #[test]
185 pub(super) fn test_aggressive_config_larger_limits() {
186 let agg = PartialEvalConfig::aggressive();
187 let def = PartialEvalConfig::default();
188 assert!(agg.max_specializations >= def.max_specializations);
189 }
190 #[test]
191 pub(super) fn test_conservative_config_smaller_limits() {
192 let con = PartialEvalConfig::conservative();
193 assert!(!con.specialize_hot_paths);
194 }
195 #[test]
196 pub(super) fn test_eval_return_lit() {
197 let mut pe = PartialEvaluator::default_eval();
198 let mut env = BindingEnv::new();
199 let expr = make_return_nat(99);
200 let (new_expr, pv) = pe.eval_expr(&expr, &mut env, 0);
201 assert!(pv.is_known());
202 assert_eq!(new_expr, make_return_nat(99));
203 }
204 #[test]
205 pub(super) fn test_eval_let_lit_binds_known() {
206 let mut pe = PartialEvaluator::default_eval();
207 let mut env = BindingEnv::new();
208 let expr = make_nat_lit(0, 7, make_return_nat(0));
209 let (_new_expr, _pv) = pe.eval_expr(&expr, &mut env, 0);
210 assert_eq!(
211 env.lookup(LcnfVarId(0)),
212 &PartialValue::Known(LcnfLit::Nat(7))
213 );
214 }
215 #[test]
216 pub(super) fn test_eval_unreachable_gives_contradiction() {
217 let mut pe = PartialEvaluator::default_eval();
218 let mut env = BindingEnv::new();
219 let (_, pv) = pe.eval_expr(&LcnfExpr::Unreachable, &mut env, 0);
220 assert_eq!(pv, PartialValue::Contradiction);
221 }
222 #[test]
223 pub(super) fn test_eval_case_with_known_scrutinee_eliminates_branch() {
224 let mut pe = PartialEvaluator::default_eval();
225 let mut env = BindingEnv::new();
226 env.bind(LcnfVarId(0), PartialValue::Known(LcnfLit::Nat(0)));
227 let alts = vec![
228 LcnfAlt {
229 ctor_name: "zero".to_string(),
230 ctor_tag: 0,
231 params: vec![],
232 body: make_return_nat(10),
233 },
234 LcnfAlt {
235 ctor_name: "succ".to_string(),
236 ctor_tag: 1,
237 params: vec![make_param(2, "n")],
238 body: make_return_nat(20),
239 },
240 ];
241 let result = pe.try_eval_case(&LcnfVarId(0), &alts, &None, &mut env, 0);
242 assert!(result.is_some());
243 let (expr, _) = result.expect("expected Some/Ok value");
244 assert_eq!(expr, make_return_nat(10));
245 assert_eq!(pe.report().branches_eliminated, 1);
246 }
247 #[test]
248 pub(super) fn test_eval_case_unknown_scrutinee_keeps_all_branches() {
249 let mut pe = PartialEvaluator::default_eval();
250 let mut env = BindingEnv::new();
251 env.bind(LcnfVarId(0), PartialValue::Unknown);
252 let case_expr = LcnfExpr::Case {
253 scrutinee: LcnfVarId(0),
254 scrutinee_ty: LcnfType::Nat,
255 alts: vec![
256 LcnfAlt {
257 ctor_name: "a".to_string(),
258 ctor_tag: 0,
259 params: vec![],
260 body: make_return_nat(1),
261 },
262 LcnfAlt {
263 ctor_name: "b".to_string(),
264 ctor_tag: 1,
265 params: vec![],
266 body: make_return_nat(2),
267 },
268 ],
269 default: None,
270 };
271 let (new_expr, _) = pe.eval_expr(&case_expr, &mut env, 0);
272 if let LcnfExpr::Case { alts, .. } = new_expr {
273 assert_eq!(alts.len(), 2);
274 } else {
275 panic!("Expected Case expression");
276 }
277 }
278 #[test]
279 pub(super) fn test_specialize_creates_new_decl() {
280 let mut pe = PartialEvaluator::default_eval();
281 let decl = make_decl(
282 "double",
283 vec![make_param(0, "n")],
284 LcnfExpr::Return(LcnfArg::Var(LcnfVarId(0))),
285 );
286 pe.known_fns.insert("double".to_string(), decl);
287 let result = pe.specialize_function("double", vec![PartialValue::Known(LcnfLit::Nat(5))]);
288 assert!(result.is_some());
289 let spec = result.expect("spec should be Some/Ok");
290 assert!(spec.name.contains("double"));
291 assert_eq!(pe.report().functions_specialized, 1);
292 }
293 #[test]
294 pub(super) fn test_specialize_unknown_function_returns_none() {
295 let mut pe = PartialEvaluator::default_eval();
296 let result = pe.specialize_function("nonexistent", vec![PartialValue::Unknown]);
297 assert!(result.is_none());
298 }
299 #[test]
300 pub(super) fn test_specialize_drops_static_params() {
301 let mut pe = PartialEvaluator::default_eval();
302 let decl = make_decl(
303 "f",
304 vec![make_param(0, "x"), make_param(1, "y")],
305 make_return_nat(0),
306 );
307 pe.known_fns.insert("f".to_string(), decl);
308 let spec = pe
309 .specialize_function(
310 "f",
311 vec![PartialValue::Known(LcnfLit::Nat(10)), PartialValue::Unknown],
312 )
313 .expect("operation should succeed");
314 assert_eq!(spec.params.len(), 1);
315 }
316 #[test]
317 pub(super) fn test_run_empty_decls() {
318 let mut pe = PartialEvaluator::default_eval();
319 let mut decls: Vec<LcnfFunDecl> = vec![];
320 pe.run(&mut decls);
321 assert_eq!(pe.report().total_optimizations(), 0);
322 }
323 #[test]
324 pub(super) fn test_run_counts_constants() {
325 let mut pe = PartialEvaluator::default_eval();
326 let body = make_nat_lit(0, 42, make_return_nat(0));
327 let decl = make_decl("g", vec![], body);
328 let mut decls = vec![decl];
329 pe.run(&mut decls);
330 assert!(pe.report().constants_computed > 0);
331 }
332 #[test]
333 pub(super) fn test_report_merge() {
334 let mut r1 = PartialEvalReport {
335 branches_eliminated: 3,
336 functions_specialized: 1,
337 constants_computed: 5,
338 memo_hits: 2,
339 lets_removed: 0,
340 };
341 let r2 = PartialEvalReport {
342 branches_eliminated: 7,
343 functions_specialized: 2,
344 constants_computed: 3,
345 memo_hits: 1,
346 lets_removed: 4,
347 };
348 r1.merge(&r2);
349 assert_eq!(r1.branches_eliminated, 10);
350 assert_eq!(r1.functions_specialized, 3);
351 assert_eq!(r1.lets_removed, 4);
352 }
353 #[test]
354 pub(super) fn test_report_total_optimizations() {
355 let r = PartialEvalReport {
356 branches_eliminated: 2,
357 functions_specialized: 1,
358 constants_computed: 3,
359 memo_hits: 10,
360 lets_removed: 1,
361 };
362 assert_eq!(r.total_optimizations(), 7);
363 }
364 #[test]
365 pub(super) fn test_report_summary_contains_fields() {
366 let r = PartialEvalReport {
367 branches_eliminated: 4,
368 functions_specialized: 2,
369 constants_computed: 6,
370 memo_hits: 3,
371 lets_removed: 1,
372 };
373 let s = r.summary();
374 assert!(s.contains("branches_elim=4"));
375 assert!(s.contains("specialized=2"));
376 }
377 #[test]
378 pub(super) fn test_binding_time_static_for_known() {
379 assert_eq!(
380 BindingTime::from_partial(&PartialValue::Known(LcnfLit::Nat(0))),
381 BindingTime::Static
382 );
383 }
384 #[test]
385 pub(super) fn test_binding_time_dynamic_for_unknown() {
386 assert_eq!(
387 BindingTime::from_partial(&PartialValue::Unknown),
388 BindingTime::Dynamic
389 );
390 }
391 #[test]
392 pub(super) fn test_binding_time_mixed_for_partial() {
393 let pv = PartialValue::Partial(vec![
394 PartialValue::Known(LcnfLit::Nat(1)),
395 PartialValue::Unknown,
396 ]);
397 assert_eq!(BindingTime::from_partial(&pv), BindingTime::Mixed);
398 }
399 #[test]
400 pub(super) fn test_analyze_binding_times_length() {
401 let decl = make_decl(
402 "h",
403 vec![make_param(0, "a"), make_param(1, "b")],
404 make_return_nat(0),
405 );
406 let times = analyze_binding_times(
407 &decl,
408 &[PartialValue::Known(LcnfLit::Nat(1)), PartialValue::Unknown],
409 );
410 assert_eq!(times.len(), 2);
411 assert_eq!(times[0], BindingTime::Static);
412 assert_eq!(times[1], BindingTime::Dynamic);
413 }
414 #[test]
415 pub(super) fn test_aggressive_prop_removes_let() {
416 let mut cfg = PartialEvalConfig::default();
417 cfg.aggressive_const_prop = true;
418 let mut pe = PartialEvaluator::new(cfg);
419 let mut env = BindingEnv::new();
420 let expr = LcnfExpr::Let {
421 id: LcnfVarId(0),
422 name: "x".to_string(),
423 ty: LcnfType::Nat,
424 value: LcnfLetValue::Lit(LcnfLit::Nat(5)),
425 body: Box::new(LcnfExpr::Return(LcnfArg::Var(LcnfVarId(0)))),
426 };
427 let (new_expr, _) = pe.eval_expr(&expr, &mut env, 0);
428 assert_eq!(pe.report().lets_removed, 1);
429 assert_eq!(new_expr, LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(5))));
430 }
431}
432#[cfg(test)]
433mod PE_infra_tests {
434 use super::*;
435 #[test]
436 pub(super) fn test_pass_config() {
437 let config = PEPassConfig::new("test_pass", PEPassPhase::Transformation);
438 assert!(config.enabled);
439 assert!(config.phase.is_modifying());
440 assert_eq!(config.phase.name(), "transformation");
441 }
442 #[test]
443 pub(super) fn test_pass_stats() {
444 let mut stats = PEPassStats::new();
445 stats.record_run(10, 100, 3);
446 stats.record_run(20, 200, 5);
447 assert_eq!(stats.total_runs, 2);
448 assert!((stats.average_changes_per_run() - 15.0).abs() < 0.01);
449 assert!((stats.success_rate() - 1.0).abs() < 0.01);
450 let s = stats.format_summary();
451 assert!(s.contains("Runs: 2/2"));
452 }
453 #[test]
454 pub(super) fn test_pass_registry() {
455 let mut reg = PEPassRegistry::new();
456 reg.register(PEPassConfig::new("pass_a", PEPassPhase::Analysis));
457 reg.register(PEPassConfig::new("pass_b", PEPassPhase::Transformation).disabled());
458 assert_eq!(reg.total_passes(), 2);
459 assert_eq!(reg.enabled_count(), 1);
460 reg.update_stats("pass_a", 5, 50, 2);
461 let stats = reg.get_stats("pass_a").expect("stats should exist");
462 assert_eq!(stats.total_changes, 5);
463 }
464 #[test]
465 pub(super) fn test_analysis_cache() {
466 let mut cache = PEAnalysisCache::new(10);
467 cache.insert("key1".to_string(), vec![1, 2, 3]);
468 assert!(cache.get("key1").is_some());
469 assert!(cache.get("key2").is_none());
470 assert!((cache.hit_rate() - 0.5).abs() < 0.01);
471 cache.invalidate("key1");
472 assert!(!cache.entries["key1"].valid);
473 assert_eq!(cache.size(), 1);
474 }
475 #[test]
476 pub(super) fn test_worklist() {
477 let mut wl = PEWorklist::new();
478 assert!(wl.push(1));
479 assert!(wl.push(2));
480 assert!(!wl.push(1));
481 assert_eq!(wl.len(), 2);
482 assert_eq!(wl.pop(), Some(1));
483 assert!(!wl.contains(1));
484 assert!(wl.contains(2));
485 }
486 #[test]
487 pub(super) fn test_dominator_tree() {
488 let mut dt = PEDominatorTree::new(5);
489 dt.set_idom(1, 0);
490 dt.set_idom(2, 0);
491 dt.set_idom(3, 1);
492 assert!(dt.dominates(0, 3));
493 assert!(dt.dominates(1, 3));
494 assert!(!dt.dominates(2, 3));
495 assert!(dt.dominates(3, 3));
496 }
497 #[test]
498 pub(super) fn test_liveness() {
499 let mut liveness = PELivenessInfo::new(3);
500 liveness.add_def(0, 1);
501 liveness.add_use(1, 1);
502 assert!(liveness.defs[0].contains(&1));
503 assert!(liveness.uses[1].contains(&1));
504 }
505 #[test]
506 pub(super) fn test_constant_folding() {
507 assert_eq!(PEConstantFoldingHelper::fold_add_i64(3, 4), Some(7));
508 assert_eq!(PEConstantFoldingHelper::fold_div_i64(10, 0), None);
509 assert_eq!(PEConstantFoldingHelper::fold_div_i64(10, 2), Some(5));
510 assert_eq!(
511 PEConstantFoldingHelper::fold_bitand_i64(0b1100, 0b1010),
512 0b1000
513 );
514 assert_eq!(PEConstantFoldingHelper::fold_bitnot_i64(0), -1);
515 }
516 #[test]
517 pub(super) fn test_dep_graph() {
518 let mut g = PEDepGraph::new();
519 g.add_dep(1, 2);
520 g.add_dep(2, 3);
521 g.add_dep(1, 3);
522 assert_eq!(g.dependencies_of(2), vec![1]);
523 let topo = g.topological_sort();
524 assert_eq!(topo.len(), 3);
525 assert!(!g.has_cycle());
526 let pos: std::collections::HashMap<u32, usize> =
527 topo.iter().enumerate().map(|(i, &n)| (n, i)).collect();
528 assert!(pos[&1] < pos[&2]);
529 assert!(pos[&1] < pos[&3]);
530 assert!(pos[&2] < pos[&3]);
531 }
532}
533#[cfg(test)]
534mod peext_pass_tests {
535 use super::*;
536 #[test]
537 pub(super) fn test_peext_phase_order() {
538 assert_eq!(PEExtPassPhase::Early.order(), 0);
539 assert_eq!(PEExtPassPhase::Middle.order(), 1);
540 assert_eq!(PEExtPassPhase::Late.order(), 2);
541 assert_eq!(PEExtPassPhase::Finalize.order(), 3);
542 assert!(PEExtPassPhase::Early.is_early());
543 assert!(!PEExtPassPhase::Early.is_late());
544 }
545 #[test]
546 pub(super) fn test_peext_config_builder() {
547 let c = PEExtPassConfig::new("p")
548 .with_phase(PEExtPassPhase::Late)
549 .with_max_iter(50)
550 .with_debug(1);
551 assert_eq!(c.name, "p");
552 assert_eq!(c.max_iterations, 50);
553 assert!(c.is_debug_enabled());
554 assert!(c.enabled);
555 let c2 = c.disabled();
556 assert!(!c2.enabled);
557 }
558 #[test]
559 pub(super) fn test_peext_stats() {
560 let mut s = PEExtPassStats::new();
561 s.visit();
562 s.visit();
563 s.modify();
564 s.iterate();
565 assert_eq!(s.nodes_visited, 2);
566 assert_eq!(s.nodes_modified, 1);
567 assert!(s.changed);
568 assert_eq!(s.iterations, 1);
569 let e = s.efficiency();
570 assert!((e - 0.5).abs() < 1e-9);
571 }
572 #[test]
573 pub(super) fn test_peext_registry() {
574 let mut r = PEExtPassRegistry::new();
575 r.register(PEExtPassConfig::new("a").with_phase(PEExtPassPhase::Early));
576 r.register(PEExtPassConfig::new("b").disabled());
577 assert_eq!(r.len(), 2);
578 assert_eq!(r.enabled_passes().len(), 1);
579 assert_eq!(r.passes_in_phase(&PEExtPassPhase::Early).len(), 1);
580 }
581 #[test]
582 pub(super) fn test_peext_cache() {
583 let mut c = PEExtCache::new(4);
584 assert!(c.get(99).is_none());
585 c.put(99, vec![1, 2, 3]);
586 let v = c.get(99).expect("v should be present in map");
587 assert_eq!(v, &[1u8, 2, 3]);
588 assert!(c.hit_rate() > 0.0);
589 assert_eq!(c.live_count(), 1);
590 }
591 #[test]
592 pub(super) fn test_peext_worklist() {
593 let mut w = PEExtWorklist::new(10);
594 w.push(5);
595 w.push(3);
596 w.push(5);
597 assert_eq!(w.len(), 2);
598 assert!(w.contains(5));
599 let first = w.pop().expect("first should be available to pop");
600 assert!(!w.contains(first));
601 }
602 #[test]
603 pub(super) fn test_peext_dom_tree() {
604 let mut dt = PEExtDomTree::new(5);
605 dt.set_idom(1, 0);
606 dt.set_idom(2, 0);
607 dt.set_idom(3, 1);
608 dt.set_idom(4, 1);
609 assert!(dt.dominates(0, 3));
610 assert!(dt.dominates(1, 4));
611 assert!(!dt.dominates(2, 3));
612 assert_eq!(dt.depth_of(3), 2);
613 }
614 #[test]
615 pub(super) fn test_peext_liveness() {
616 let mut lv = PEExtLiveness::new(3);
617 lv.add_def(0, 1);
618 lv.add_use(1, 1);
619 assert!(lv.var_is_def_in_block(0, 1));
620 assert!(lv.var_is_used_in_block(1, 1));
621 assert!(!lv.var_is_def_in_block(1, 1));
622 }
623 #[test]
624 pub(super) fn test_peext_const_folder() {
625 let mut cf = PEExtConstFolder::new();
626 assert_eq!(cf.add_i64(3, 4), Some(7));
627 assert_eq!(cf.div_i64(10, 0), None);
628 assert_eq!(cf.mul_i64(6, 7), Some(42));
629 assert_eq!(cf.and_i64(0b1100, 0b1010), 0b1000);
630 assert_eq!(cf.fold_count(), 3);
631 assert_eq!(cf.failure_count(), 1);
632 }
633 #[test]
634 pub(super) fn test_peext_dep_graph() {
635 let mut g = PEExtDepGraph::new(4);
636 g.add_edge(0, 1);
637 g.add_edge(1, 2);
638 g.add_edge(2, 3);
639 assert!(!g.has_cycle());
640 assert_eq!(g.topo_sort(), Some(vec![0, 1, 2, 3]));
641 assert_eq!(g.reachable(0).len(), 4);
642 let sccs = g.scc();
643 assert_eq!(sccs.len(), 4);
644 }
645}