1use crate::lcnf::{LcnfArg, LcnfExpr, LcnfFunDecl, LcnfLetValue, LcnfVarId};
6use std::collections::{HashMap, HashSet};
7
8use super::types::{
9 AffineAccess, DepEdge, DependenceAnalyser, DependenceInfo, OParConfig, OParDiagCollector,
10 OParDiagMsg, OParEmitStats, OParEventLog, OParExtCache, OParExtConstFolder, OParExtDepGraph,
11 OParExtDomTree, OParExtLiveness, OParExtPassConfig, OParExtPassPhase, OParExtPassRegistry,
12 OParExtPassStats, OParExtWorklist, OParFeatures, OParIdGen, OParIncrKey, OParNameScope,
13 OParPassTiming, OParProfiler, OParSourceBuffer, OParVersion, ParAnalysisCache,
14 ParConstantFoldingHelper, ParDepGraph, ParDominatorTree, ParLivenessInfo, ParPassConfig,
15 ParPassPhase, ParPassRegistry, ParPassStats, ParWorklist, ParallelConfig, ParallelKind,
16 ParallelPass, ParallelPattern, ParallelRegion, ParallelReport, PatternDetector,
17 ThreadSafetyInfo,
18};
19
20pub(super) fn gcd(a: u64, b: u64) -> u64 {
21 if b == 0 {
22 a
23 } else {
24 gcd(b, a % b)
25 }
26}
27pub(super) fn amdahl_speedup(p: f64, n: f64) -> f64 {
31 let p = p.clamp(0.0, 1.0);
32 let n = n.max(1.0);
33 1.0 / ((1.0 - p) + p / n)
34}
35pub(super) fn estimate_speedup_for_pattern(
36 pattern: ParallelPattern,
37 trip_count: Option<u64>,
38) -> f64 {
39 let n_cores = 8.0_f64;
40 let trip = trip_count.unwrap_or(1024) as f64;
41 let parallel_fraction = match pattern {
42 ParallelPattern::Map => 0.98,
43 ParallelPattern::Reduce => 0.85,
44 ParallelPattern::Scan => 0.75,
45 ParallelPattern::Filter => 0.90,
46 ParallelPattern::Stencil => 0.88,
47 ParallelPattern::ParallelFor => 0.95,
48 ParallelPattern::Scatter => 0.70,
49 ParallelPattern::Gather => 0.72,
50 };
51 let effective_p = parallel_fraction * (trip / (trip + 64.0));
52 amdahl_speedup(effective_p, n_cores)
53}
54#[cfg(test)]
55mod tests {
56 use super::*;
57 use crate::lcnf::{LcnfFunDecl, LcnfParam, LcnfType, LcnfVarId};
58 pub(super) fn vid(n: u64) -> LcnfVarId {
59 LcnfVarId(n)
60 }
61 pub(super) fn mk_param(n: u64, name: &str) -> LcnfParam {
62 LcnfParam {
63 id: vid(n),
64 name: name.to_string(),
65 ty: LcnfType::Nat,
66 erased: false,
67 borrowed: false,
68 }
69 }
70 pub(super) fn mk_decl(name: &str, body: LcnfExpr, recursive: bool) -> LcnfFunDecl {
71 LcnfFunDecl {
72 name: name.to_string(),
73 original_name: None,
74 params: vec![
75 mk_param(0, "arr_in"),
76 mk_param(1, "arr_out"),
77 mk_param(2, "n"),
78 ],
79 ret_type: LcnfType::Nat,
80 body,
81 is_recursive: recursive,
82 is_lifted: false,
83 inline_cost: 1,
84 }
85 }
86 pub(super) fn simple_return() -> LcnfExpr {
87 LcnfExpr::Return(LcnfArg::Lit(crate::lcnf::LcnfLit::Nat(0)))
88 }
89 pub(super) fn tail_call_body() -> LcnfExpr {
90 LcnfExpr::TailCall(LcnfArg::Var(vid(0)), vec![LcnfArg::Var(vid(1))])
91 }
92 pub(super) fn reduce_body() -> LcnfExpr {
93 LcnfExpr::Let {
94 id: vid(10),
95 name: "acc".to_string(),
96 ty: LcnfType::Nat,
97 value: LcnfLetValue::App(
98 LcnfArg::Var(vid(2)),
99 vec![LcnfArg::Var(vid(0)), LcnfArg::Var(vid(1))],
100 ),
101 body: Box::new(tail_call_body()),
102 }
103 }
104 #[test]
105 pub(super) fn parallel_kind_display() {
106 assert_eq!(ParallelKind::DataParallel.to_string(), "data-parallel");
107 assert_eq!(ParallelKind::TaskParallel.to_string(), "task-parallel");
108 assert_eq!(
109 ParallelKind::PipelineParallel.to_string(),
110 "pipeline-parallel"
111 );
112 assert_eq!(
113 ParallelKind::SpeculativeParallel.to_string(),
114 "speculative-parallel"
115 );
116 }
117 #[test]
118 pub(super) fn parallel_kind_eq() {
119 assert_eq!(ParallelKind::DataParallel, ParallelKind::DataParallel);
120 assert_ne!(ParallelKind::DataParallel, ParallelKind::TaskParallel);
121 }
122 #[test]
123 pub(super) fn parallel_pattern_display() {
124 assert_eq!(ParallelPattern::Map.to_string(), "map");
125 assert_eq!(ParallelPattern::Reduce.to_string(), "reduce");
126 assert_eq!(ParallelPattern::Scan.to_string(), "scan");
127 assert_eq!(ParallelPattern::Filter.to_string(), "filter");
128 assert_eq!(ParallelPattern::Stencil.to_string(), "stencil");
129 assert_eq!(ParallelPattern::ParallelFor.to_string(), "parallel-for");
130 assert_eq!(ParallelPattern::Scatter.to_string(), "scatter");
131 assert_eq!(ParallelPattern::Gather.to_string(), "gather");
132 }
133 #[test]
134 pub(super) fn dependence_info_empty_is_parallelizable() {
135 let info = DependenceInfo::default();
136 assert!(info.is_parallelizable());
137 assert_eq!(info.total_deps(), 0);
138 }
139 #[test]
140 pub(super) fn dependence_info_with_loop_carried_not_parallelizable() {
141 let mut info = DependenceInfo::default();
142 info.loop_carried_deps.push(DepEdge {
143 from: "a".to_string(),
144 to: "b".to_string(),
145 distance: 1,
146 });
147 assert!(!info.is_parallelizable());
148 }
149 #[test]
150 pub(super) fn dependence_info_total_counts() {
151 let mut info = DependenceInfo::default();
152 info.true_deps.push(DepEdge {
153 from: "a".to_string(),
154 to: "b".to_string(),
155 distance: 0,
156 });
157 info.anti_deps.push(DepEdge {
158 from: "c".to_string(),
159 to: "d".to_string(),
160 distance: 0,
161 });
162 info.output_deps.push(DepEdge {
163 from: "e".to_string(),
164 to: "f".to_string(),
165 distance: 0,
166 });
167 assert_eq!(info.total_deps(), 3);
168 assert!(info.is_parallelizable());
169 }
170 #[test]
171 pub(super) fn dependence_info_display() {
172 let info = DependenceInfo::default();
173 let s = info.to_string();
174 assert!(s.contains("parallelizable=true"));
175 }
176 #[test]
177 pub(super) fn affine_access_different_bases_are_independent() {
178 let a = AffineAccess {
179 base: "x".to_string(),
180 coeff: 1,
181 offset: 0,
182 is_write: true,
183 };
184 let b = AffineAccess {
185 base: "y".to_string(),
186 coeff: 1,
187 offset: 0,
188 is_write: false,
189 };
190 assert!(a.independent_from(&b));
191 }
192 #[test]
193 pub(super) fn affine_access_two_reads_are_independent() {
194 let a = AffineAccess {
195 base: "x".to_string(),
196 coeff: 1,
197 offset: 0,
198 is_write: false,
199 };
200 let b = AffineAccess {
201 base: "x".to_string(),
202 coeff: 1,
203 offset: 0,
204 is_write: false,
205 };
206 assert!(a.independent_from(&b));
207 }
208 #[test]
209 pub(super) fn affine_access_aliased_write_read_not_independent() {
210 let a = AffineAccess {
211 base: "a".to_string(),
212 coeff: 1,
213 offset: 0,
214 is_write: true,
215 };
216 let b = AffineAccess {
217 base: "a".to_string(),
218 coeff: 1,
219 offset: 0,
220 is_write: false,
221 };
222 assert!(!a.independent_from(&b));
223 }
224 #[test]
225 pub(super) fn affine_access_non_overlapping_offsets() {
226 let a = AffineAccess {
227 base: "a".to_string(),
228 coeff: 2,
229 offset: 0,
230 is_write: true,
231 };
232 let b = AffineAccess {
233 base: "a".to_string(),
234 coeff: 2,
235 offset: 1,
236 is_write: false,
237 };
238 assert!(a.independent_from(&b));
239 }
240 #[test]
241 pub(super) fn thread_safety_safe_constructor() {
242 let info = ThreadSafetyInfo::safe();
243 assert!(info.is_thread_safe);
244 assert!(info.race_conditions.is_empty());
245 assert!(info.atomic_ops_needed.is_empty());
246 }
247 #[test]
248 pub(super) fn thread_safety_unsafe_race_constructor() {
249 let info = ThreadSafetyInfo::unsafe_race("w", "r");
250 assert!(!info.is_thread_safe);
251 assert_eq!(info.race_conditions.len(), 1);
252 assert_eq!(info.race_conditions[0], ("w".to_string(), "r".to_string()));
253 }
254 #[test]
255 pub(super) fn thread_safety_display() {
256 let info = ThreadSafetyInfo::safe();
257 let s = info.to_string();
258 assert!(s.contains("safe=true"));
259 }
260 #[test]
261 pub(super) fn parallel_region_new_defaults() {
262 let r = ParallelRegion::new("foo", ParallelKind::DataParallel, ParallelPattern::Map);
263 assert_eq!(r.func_name, "foo");
264 assert_eq!(r.estimated_speedup, 1.0);
265 assert!(r.shared_vars.is_empty());
266 }
267 #[test]
268 pub(super) fn parallel_region_not_profitable_at_1x() {
269 let r = ParallelRegion::new("foo", ParallelKind::DataParallel, ParallelPattern::Map);
270 assert!(!r.is_profitable(1.5));
271 }
272 #[test]
273 pub(super) fn parallel_region_profitable_with_high_speedup() {
274 let mut r = ParallelRegion::new("foo", ParallelKind::DataParallel, ParallelPattern::Map);
275 r.estimated_speedup = 4.0;
276 assert!(r.is_profitable(1.5));
277 }
278 #[test]
279 pub(super) fn parallel_region_not_profitable_with_loop_carried_dep() {
280 let mut r = ParallelRegion::new("foo", ParallelKind::DataParallel, ParallelPattern::Map);
281 r.estimated_speedup = 4.0;
282 r.dependence_info.loop_carried_deps.push(DepEdge {
283 from: "a".to_string(),
284 to: "b".to_string(),
285 distance: 1,
286 });
287 assert!(!r.is_profitable(1.5));
288 }
289 #[test]
290 pub(super) fn parallel_region_display() {
291 let r = ParallelRegion::new("bar", ParallelKind::DataParallel, ParallelPattern::Reduce);
292 let s = r.to_string();
293 assert!(s.contains("bar"));
294 assert!(s.contains("reduce"));
295 }
296 #[test]
297 pub(super) fn amdahl_all_serial() {
298 assert!((amdahl_speedup(0.0, 8.0) - 1.0).abs() < 1e-9);
299 }
300 #[test]
301 pub(super) fn amdahl_all_parallel() {
302 let s = amdahl_speedup(1.0, 8.0);
303 assert!((s - 8.0).abs() < 1e-9);
304 }
305 #[test]
306 pub(super) fn amdahl_clamps_fraction() {
307 let s1 = amdahl_speedup(1.0, 4.0);
308 let s2 = amdahl_speedup(1.5, 4.0);
309 assert!((s1 - s2).abs() < 1e-9);
310 }
311 #[test]
312 pub(super) fn estimate_speedup_map_large_trip() {
313 let s = estimate_speedup_for_pattern(ParallelPattern::Map, Some(8192));
314 assert!(s > 1.0, "map speedup={}", s);
315 }
316 #[test]
317 pub(super) fn estimate_speedup_reduce_less_than_map() {
318 let s_map = estimate_speedup_for_pattern(ParallelPattern::Map, Some(4096));
319 let s_red = estimate_speedup_for_pattern(ParallelPattern::Reduce, Some(4096));
320 assert!(s_map > s_red, "map={} reduce={}", s_map, s_red);
321 }
322 #[test]
323 pub(super) fn pattern_detector_reduce_body() {
324 let decl = mk_decl("reduce_loop", reduce_body(), true);
325 let pat = PatternDetector::new(&decl).detect();
326 assert_eq!(pat, Some(ParallelPattern::Reduce));
327 }
328 #[test]
329 pub(super) fn pattern_detector_non_recursive_is_none() {
330 let decl = mk_decl("just_ret", simple_return(), false);
331 let pat = PatternDetector::new(&decl).detect();
332 assert!(pat.is_none());
333 }
334 #[test]
335 pub(super) fn pattern_detector_parallel_for_fallback() {
336 let decl = mk_decl("generic_loop", tail_call_body(), true);
337 let pat = PatternDetector::new(&decl).detect();
338 assert!(pat.is_some());
339 }
340 #[test]
341 pub(super) fn dependence_analyser_empty_body_no_deps() {
342 let decl = mk_decl("simple", simple_return(), false);
343 let info = DependenceAnalyser::new(&decl).analyse();
344 assert!(info.is_parallelizable());
345 }
346 #[test]
347 pub(super) fn dependence_analyser_reduce_body() {
348 let decl = mk_decl("reduce", reduce_body(), true);
349 let info = DependenceAnalyser::new(&decl).analyse();
350 let _ = info.is_parallelizable();
351 }
352 #[test]
353 pub(super) fn parallel_pass_empty_decls() {
354 let mut pass = ParallelPass::default_pass();
355 let mut decls: Vec<LcnfFunDecl> = vec![];
356 pass.run(&mut decls);
357 let report = pass.report();
358 assert_eq!(report.regions_found, 0);
359 assert_eq!(report.regions_transformed, 0);
360 }
361 #[test]
362 pub(super) fn parallel_pass_report_default_speedup() {
363 let pass = ParallelPass::default_pass();
364 let report = pass.report();
365 assert_eq!(report.estimated_total_speedup, 1.0);
366 }
367 #[test]
368 pub(super) fn parallel_pass_finds_reduce_region() {
369 let mut pass = ParallelPass::default_pass();
370 let decl = mk_decl("sum_loop", reduce_body(), true);
371 let mut decls = vec![decl];
372 pass.analyze_parallelism(&decls.clone());
373 let _ = pass.report();
374 pass.transform_to_parallel(&mut decls);
375 }
376 #[test]
377 pub(super) fn parallel_report_display() {
378 let r = ParallelReport {
379 regions_found: 3,
380 regions_transformed: 2,
381 estimated_total_speedup: 5.5,
382 race_conditions_detected: 0,
383 };
384 let s = r.to_string();
385 assert!(s.contains("found=3"));
386 assert!(s.contains("transformed=2"));
387 }
388 #[test]
389 pub(super) fn parallel_config_default() {
390 let cfg = ParallelConfig::default();
391 assert!((cfg.min_speedup_threshold - 1.5).abs() < 1e-9);
392 assert_eq!(cfg.hardware_threads, 8);
393 assert!(!cfg.allow_speculative);
394 }
395 #[test]
396 pub(super) fn gcd_basic() {
397 assert_eq!(gcd(12, 8), 4);
398 assert_eq!(gcd(7, 3), 1);
399 assert_eq!(gcd(0, 5), 5);
400 assert_eq!(gcd(5, 0), 5);
401 }
402}
403#[cfg(test)]
404mod tests_opar_extra {
405 use super::*;
406 #[test]
407 pub(super) fn test_opar_config() {
408 let mut cfg = OParConfig::new();
409 cfg.set("mode", "release");
410 cfg.set("verbose", "true");
411 assert_eq!(cfg.get("mode"), Some("release"));
412 assert!(cfg.get_bool("verbose"));
413 assert!(cfg.get_int("mode").is_none());
414 assert_eq!(cfg.len(), 2);
415 }
416 #[test]
417 pub(super) fn test_opar_source_buffer() {
418 let mut buf = OParSourceBuffer::new();
419 buf.push_line("fn main() {");
420 buf.indent();
421 buf.push_line("println!(\"hello\");");
422 buf.dedent();
423 buf.push_line("}");
424 assert!(buf.as_str().contains("fn main()"));
425 assert!(buf.as_str().contains(" println!"));
426 assert_eq!(buf.line_count(), 3);
427 buf.reset();
428 assert!(buf.is_empty());
429 }
430 #[test]
431 pub(super) fn test_opar_name_scope() {
432 let mut scope = OParNameScope::new();
433 assert!(scope.declare("x"));
434 assert!(!scope.declare("x"));
435 assert!(scope.is_declared("x"));
436 let scope = scope.push_scope();
437 assert_eq!(scope.depth(), 1);
438 let mut scope = scope.pop_scope();
439 assert_eq!(scope.depth(), 0);
440 scope.declare("y");
441 assert_eq!(scope.len(), 2);
442 }
443 #[test]
444 pub(super) fn test_opar_diag_collector() {
445 let mut col = OParDiagCollector::new();
446 col.emit(OParDiagMsg::warning("pass_a", "slow"));
447 col.emit(OParDiagMsg::error("pass_b", "fatal"));
448 assert!(col.has_errors());
449 assert_eq!(col.errors().len(), 1);
450 assert_eq!(col.warnings().len(), 1);
451 col.clear();
452 assert!(col.is_empty());
453 }
454 #[test]
455 pub(super) fn test_opar_id_gen() {
456 let mut gen = OParIdGen::new();
457 assert_eq!(gen.next_id(), 0);
458 assert_eq!(gen.next_id(), 1);
459 gen.skip(10);
460 assert_eq!(gen.next_id(), 12);
461 gen.reset();
462 assert_eq!(gen.peek_next(), 0);
463 }
464 #[test]
465 pub(super) fn test_opar_incr_key() {
466 let k1 = OParIncrKey::new(100, 200);
467 let k2 = OParIncrKey::new(100, 200);
468 let k3 = OParIncrKey::new(999, 200);
469 assert!(k1.matches(&k2));
470 assert!(!k1.matches(&k3));
471 }
472 #[test]
473 pub(super) fn test_opar_profiler() {
474 let mut p = OParProfiler::new();
475 p.record(OParPassTiming::new("pass_a", 1000, 50, 200, 100));
476 p.record(OParPassTiming::new("pass_b", 500, 30, 100, 200));
477 assert_eq!(p.total_elapsed_us(), 1500);
478 assert_eq!(
479 p.slowest_pass()
480 .expect("slowest pass should exist")
481 .pass_name,
482 "pass_a"
483 );
484 assert_eq!(p.profitable_passes().len(), 1);
485 }
486 #[test]
487 pub(super) fn test_opar_event_log() {
488 let mut log = OParEventLog::new(3);
489 log.push("event1");
490 log.push("event2");
491 log.push("event3");
492 assert_eq!(log.len(), 3);
493 log.push("event4");
494 assert_eq!(log.len(), 3);
495 assert_eq!(
496 log.iter()
497 .next()
498 .expect("iterator should have next element"),
499 "event2"
500 );
501 }
502 #[test]
503 pub(super) fn test_opar_version() {
504 let v = OParVersion::new(1, 2, 3).with_pre("alpha");
505 assert!(!v.is_stable());
506 assert_eq!(format!("{}", v), "1.2.3-alpha");
507 let stable = OParVersion::new(2, 0, 0);
508 assert!(stable.is_stable());
509 assert!(stable.is_compatible_with(&OParVersion::new(2, 0, 0)));
510 assert!(!stable.is_compatible_with(&OParVersion::new(3, 0, 0)));
511 }
512 #[test]
513 pub(super) fn test_opar_features() {
514 let mut f = OParFeatures::new();
515 f.enable("sse2");
516 f.enable("avx2");
517 assert!(f.is_enabled("sse2"));
518 assert!(!f.is_enabled("avx512"));
519 f.disable("avx2");
520 assert!(!f.is_enabled("avx2"));
521 let mut g = OParFeatures::new();
522 g.enable("sse2");
523 g.enable("neon");
524 let union = f.union(&g);
525 assert!(union.is_enabled("sse2") && union.is_enabled("neon"));
526 let inter = f.intersection(&g);
527 assert!(inter.is_enabled("sse2"));
528 }
529 #[test]
530 pub(super) fn test_opar_emit_stats() {
531 let mut s = OParEmitStats::new();
532 s.bytes_emitted = 50_000;
533 s.items_emitted = 500;
534 s.elapsed_ms = 100;
535 assert!(s.is_clean());
536 assert!((s.throughput_bps() - 500_000.0).abs() < 1.0);
537 let disp = format!("{}", s);
538 assert!(disp.contains("bytes=50000"));
539 }
540}
541#[cfg(test)]
542mod Par_infra_tests {
543 use super::*;
544 #[test]
545 pub(super) fn test_pass_config() {
546 let config = ParPassConfig::new("test_pass", ParPassPhase::Transformation);
547 assert!(config.enabled);
548 assert!(config.phase.is_modifying());
549 assert_eq!(config.phase.name(), "transformation");
550 }
551 #[test]
552 pub(super) fn test_pass_stats() {
553 let mut stats = ParPassStats::new();
554 stats.record_run(10, 100, 3);
555 stats.record_run(20, 200, 5);
556 assert_eq!(stats.total_runs, 2);
557 assert!((stats.average_changes_per_run() - 15.0).abs() < 0.01);
558 assert!((stats.success_rate() - 1.0).abs() < 0.01);
559 let s = stats.format_summary();
560 assert!(s.contains("Runs: 2/2"));
561 }
562 #[test]
563 pub(super) fn test_pass_registry() {
564 let mut reg = ParPassRegistry::new();
565 reg.register(ParPassConfig::new("pass_a", ParPassPhase::Analysis));
566 reg.register(ParPassConfig::new("pass_b", ParPassPhase::Transformation).disabled());
567 assert_eq!(reg.total_passes(), 2);
568 assert_eq!(reg.enabled_count(), 1);
569 reg.update_stats("pass_a", 5, 50, 2);
570 let stats = reg.get_stats("pass_a").expect("stats should exist");
571 assert_eq!(stats.total_changes, 5);
572 }
573 #[test]
574 pub(super) fn test_analysis_cache() {
575 let mut cache = ParAnalysisCache::new(10);
576 cache.insert("key1".to_string(), vec![1, 2, 3]);
577 assert!(cache.get("key1").is_some());
578 assert!(cache.get("key2").is_none());
579 assert!((cache.hit_rate() - 0.5).abs() < 0.01);
580 cache.invalidate("key1");
581 assert!(!cache.entries["key1"].valid);
582 assert_eq!(cache.size(), 1);
583 }
584 #[test]
585 pub(super) fn test_worklist() {
586 let mut wl = ParWorklist::new();
587 assert!(wl.push(1));
588 assert!(wl.push(2));
589 assert!(!wl.push(1));
590 assert_eq!(wl.len(), 2);
591 assert_eq!(wl.pop(), Some(1));
592 assert!(!wl.contains(1));
593 assert!(wl.contains(2));
594 }
595 #[test]
596 pub(super) fn test_dominator_tree() {
597 let mut dt = ParDominatorTree::new(5);
598 dt.set_idom(1, 0);
599 dt.set_idom(2, 0);
600 dt.set_idom(3, 1);
601 assert!(dt.dominates(0, 3));
602 assert!(dt.dominates(1, 3));
603 assert!(!dt.dominates(2, 3));
604 assert!(dt.dominates(3, 3));
605 }
606 #[test]
607 pub(super) fn test_liveness() {
608 let mut liveness = ParLivenessInfo::new(3);
609 liveness.add_def(0, 1);
610 liveness.add_use(1, 1);
611 assert!(liveness.defs[0].contains(&1));
612 assert!(liveness.uses[1].contains(&1));
613 }
614 #[test]
615 pub(super) fn test_constant_folding() {
616 assert_eq!(ParConstantFoldingHelper::fold_add_i64(3, 4), Some(7));
617 assert_eq!(ParConstantFoldingHelper::fold_div_i64(10, 0), None);
618 assert_eq!(ParConstantFoldingHelper::fold_div_i64(10, 2), Some(5));
619 assert_eq!(
620 ParConstantFoldingHelper::fold_bitand_i64(0b1100, 0b1010),
621 0b1000
622 );
623 assert_eq!(ParConstantFoldingHelper::fold_bitnot_i64(0), -1);
624 }
625 #[test]
626 pub(super) fn test_dep_graph() {
627 let mut g = ParDepGraph::new();
628 g.add_dep(1, 2);
629 g.add_dep(2, 3);
630 g.add_dep(1, 3);
631 assert_eq!(g.dependencies_of(2), vec![1]);
632 let topo = g.topological_sort();
633 assert_eq!(topo.len(), 3);
634 assert!(!g.has_cycle());
635 let pos: std::collections::HashMap<u32, usize> =
636 topo.iter().enumerate().map(|(i, &n)| (n, i)).collect();
637 assert!(pos[&1] < pos[&2]);
638 assert!(pos[&1] < pos[&3]);
639 assert!(pos[&2] < pos[&3]);
640 }
641}
642#[cfg(test)]
643mod oparext_pass_tests {
644 use super::*;
645 #[test]
646 pub(super) fn test_oparext_phase_order() {
647 assert_eq!(OParExtPassPhase::Early.order(), 0);
648 assert_eq!(OParExtPassPhase::Middle.order(), 1);
649 assert_eq!(OParExtPassPhase::Late.order(), 2);
650 assert_eq!(OParExtPassPhase::Finalize.order(), 3);
651 assert!(OParExtPassPhase::Early.is_early());
652 assert!(!OParExtPassPhase::Early.is_late());
653 }
654 #[test]
655 pub(super) fn test_oparext_config_builder() {
656 let c = OParExtPassConfig::new("p")
657 .with_phase(OParExtPassPhase::Late)
658 .with_max_iter(50)
659 .with_debug(1);
660 assert_eq!(c.name, "p");
661 assert_eq!(c.max_iterations, 50);
662 assert!(c.is_debug_enabled());
663 assert!(c.enabled);
664 let c2 = c.disabled();
665 assert!(!c2.enabled);
666 }
667 #[test]
668 pub(super) fn test_oparext_stats() {
669 let mut s = OParExtPassStats::new();
670 s.visit();
671 s.visit();
672 s.modify();
673 s.iterate();
674 assert_eq!(s.nodes_visited, 2);
675 assert_eq!(s.nodes_modified, 1);
676 assert!(s.changed);
677 assert_eq!(s.iterations, 1);
678 let e = s.efficiency();
679 assert!((e - 0.5).abs() < 1e-9);
680 }
681 #[test]
682 pub(super) fn test_oparext_registry() {
683 let mut r = OParExtPassRegistry::new();
684 r.register(OParExtPassConfig::new("a").with_phase(OParExtPassPhase::Early));
685 r.register(OParExtPassConfig::new("b").disabled());
686 assert_eq!(r.len(), 2);
687 assert_eq!(r.enabled_passes().len(), 1);
688 assert_eq!(r.passes_in_phase(&OParExtPassPhase::Early).len(), 1);
689 }
690 #[test]
691 pub(super) fn test_oparext_cache() {
692 let mut c = OParExtCache::new(4);
693 assert!(c.get(99).is_none());
694 c.put(99, vec![1, 2, 3]);
695 let v = c.get(99).expect("v should be present in map");
696 assert_eq!(v, &[1u8, 2, 3]);
697 assert!(c.hit_rate() > 0.0);
698 assert_eq!(c.live_count(), 1);
699 }
700 #[test]
701 pub(super) fn test_oparext_worklist() {
702 let mut w = OParExtWorklist::new(10);
703 w.push(5);
704 w.push(3);
705 w.push(5);
706 assert_eq!(w.len(), 2);
707 assert!(w.contains(5));
708 let first = w.pop().expect("first should be available to pop");
709 assert!(!w.contains(first));
710 }
711 #[test]
712 pub(super) fn test_oparext_dom_tree() {
713 let mut dt = OParExtDomTree::new(5);
714 dt.set_idom(1, 0);
715 dt.set_idom(2, 0);
716 dt.set_idom(3, 1);
717 dt.set_idom(4, 1);
718 assert!(dt.dominates(0, 3));
719 assert!(dt.dominates(1, 4));
720 assert!(!dt.dominates(2, 3));
721 assert_eq!(dt.depth_of(3), 2);
722 }
723 #[test]
724 pub(super) fn test_oparext_liveness() {
725 let mut lv = OParExtLiveness::new(3);
726 lv.add_def(0, 1);
727 lv.add_use(1, 1);
728 assert!(lv.var_is_def_in_block(0, 1));
729 assert!(lv.var_is_used_in_block(1, 1));
730 assert!(!lv.var_is_def_in_block(1, 1));
731 }
732 #[test]
733 pub(super) fn test_oparext_const_folder() {
734 let mut cf = OParExtConstFolder::new();
735 assert_eq!(cf.add_i64(3, 4), Some(7));
736 assert_eq!(cf.div_i64(10, 0), None);
737 assert_eq!(cf.mul_i64(6, 7), Some(42));
738 assert_eq!(cf.and_i64(0b1100, 0b1010), 0b1000);
739 assert_eq!(cf.fold_count(), 3);
740 assert_eq!(cf.failure_count(), 1);
741 }
742 #[test]
743 pub(super) fn test_oparext_dep_graph() {
744 let mut g = OParExtDepGraph::new(4);
745 g.add_edge(0, 1);
746 g.add_edge(1, 2);
747 g.add_edge(2, 3);
748 assert!(!g.has_cycle());
749 assert_eq!(g.topo_sort(), Some(vec![0, 1, 2, 3]));
750 assert_eq!(g.reachable(0).len(), 4);
751 let sccs = g.scc();
752 assert_eq!(sccs.len(), 4);
753 }
754}