1use super::types::{
6 AccessPattern, CacheLevel, CacheOptPass, CacheOptReport, LoopTile, MemoryAccess,
7 OCAnalysisCache, OCConstantFoldingHelper, OCDepGraph, OCDominatorTree, OCLivenessInfo,
8 OCPassConfig, OCPassPhase, OCPassRegistry, OCPassStats, OCWorklist, OCacheExtCache,
9 OCacheExtConstFolder, OCacheExtDepGraph, OCacheExtDomTree, OCacheExtLiveness,
10 OCacheExtPassConfig, OCacheExtPassPhase, OCacheExtPassRegistry, OCacheExtPassStats,
11 OCacheExtWorklist, OCacheX2Cache, OCacheX2ConstFolder, OCacheX2DepGraph, OCacheX2DomTree,
12 OCacheX2Liveness, OCacheX2PassConfig, OCacheX2PassPhase, OCacheX2PassRegistry,
13 OCacheX2PassStats, OCacheX2Worklist, PrefetchHint, PrefetchType, StructLayout,
14};
15
16#[cfg(test)]
17mod tests {
18 use super::*;
19 #[test]
20 pub(super) fn cache_level_capacity_ordering() {
21 assert!(CacheLevel::L1.capacity_bytes() < CacheLevel::L2.capacity_bytes());
22 assert!(CacheLevel::L2.capacity_bytes() < CacheLevel::L3.capacity_bytes());
23 }
24 #[test]
25 pub(super) fn cache_level_latency_ordering() {
26 assert!(CacheLevel::L1.latency_cycles() < CacheLevel::L2.latency_cycles());
27 assert!(CacheLevel::L2.latency_cycles() < CacheLevel::L3.latency_cycles());
28 assert!(CacheLevel::L3.latency_cycles() < CacheLevel::Ram.latency_cycles());
29 }
30 #[test]
31 pub(super) fn access_pattern_friendliness() {
32 assert!(AccessPattern::Sequential.is_cache_friendly());
33 assert!(AccessPattern::Broadcast.is_cache_friendly());
34 assert!(AccessPattern::Strided(8).is_cache_friendly());
35 assert!(!AccessPattern::Strided(128).is_cache_friendly());
36 assert!(!AccessPattern::Random.is_cache_friendly());
37 }
38 #[test]
39 pub(super) fn struct_layout_metrics() {
40 let layout = StructLayout {
41 struct_name: "Foo".into(),
42 fields: vec![("a".into(), 8), ("b".into(), 8)],
43 total_size: 16,
44 alignment: 8,
45 };
46 assert_eq!(layout.padding_bytes(), 0);
47 assert_eq!(layout.cache_lines_used(), 1);
48 assert!(!layout.is_cache_aligned());
49 }
50 #[test]
51 pub(super) fn struct_layout_cache_aligned() {
52 let layout = StructLayout {
53 struct_name: "Aligned".into(),
54 fields: vec![("x".into(), 64)],
55 total_size: 64,
56 alignment: 64,
57 };
58 assert!(layout.is_cache_aligned());
59 assert_eq!(layout.cache_lines_used(), 1);
60 }
61 #[test]
62 pub(super) fn loop_tile_names() {
63 let tile = LoopTile::new("i", 64);
64 assert_eq!(tile.tile_var, "i_tile");
65 assert_eq!(tile.intra_var, "i_intra");
66 assert_eq!(tile.tile_size, 64);
67 }
68 #[test]
69 pub(super) fn cache_opt_report_summary() {
70 let report = CacheOptReport {
71 num_loops_tiled: 3,
72 num_prefetches_inserted: 12,
73 estimated_cache_miss_reduction: 0.25,
74 };
75 let s = report.summary();
76 assert!(s.contains("3 loops tiled"));
77 assert!(s.contains("12 prefetches"));
78 assert!(s.contains("25.0%"));
79 }
80 #[test]
81 pub(super) fn memory_access_cache_friendly() {
82 let seq = MemoryAccess::new("arr", 0, AccessPattern::Sequential, Some(8), 100);
83 assert!(seq.is_cache_friendly());
84 let rnd = MemoryAccess::new("arr", 0, AccessPattern::Random, None, 10);
85 assert!(!rnd.is_cache_friendly());
86 }
87 #[test]
88 pub(super) fn prefetch_hint_construction() {
89 let hint = PrefetchHint::new("&arr[8]", 8, PrefetchType::Read);
90 assert_eq!(hint.distance, 8);
91 assert_eq!(hint.hint_type, PrefetchType::Read);
92 }
93 #[test]
94 pub(super) fn cache_opt_pass_default() {
95 let pass = CacheOptPass::default();
96 assert_eq!(pass.config.cache_line_size, 64);
97 assert_eq!(pass.config.prefetch_distance, 8);
98 assert!(pass.config.enable_prefetch);
99 }
100}
101#[cfg(test)]
102mod OC_infra_tests {
103 use super::*;
104 #[test]
105 pub(super) fn test_pass_config() {
106 let config = OCPassConfig::new("test_pass", OCPassPhase::Transformation);
107 assert!(config.enabled);
108 assert!(config.phase.is_modifying());
109 assert_eq!(config.phase.name(), "transformation");
110 }
111 #[test]
112 pub(super) fn test_pass_stats() {
113 let mut stats = OCPassStats::new();
114 stats.record_run(10, 100, 3);
115 stats.record_run(20, 200, 5);
116 assert_eq!(stats.total_runs, 2);
117 assert!((stats.average_changes_per_run() - 15.0).abs() < 0.01);
118 assert!((stats.success_rate() - 1.0).abs() < 0.01);
119 let s = stats.format_summary();
120 assert!(s.contains("Runs: 2/2"));
121 }
122 #[test]
123 pub(super) fn test_pass_registry() {
124 let mut reg = OCPassRegistry::new();
125 reg.register(OCPassConfig::new("pass_a", OCPassPhase::Analysis));
126 reg.register(OCPassConfig::new("pass_b", OCPassPhase::Transformation).disabled());
127 assert_eq!(reg.total_passes(), 2);
128 assert_eq!(reg.enabled_count(), 1);
129 reg.update_stats("pass_a", 5, 50, 2);
130 let stats = reg.get_stats("pass_a").expect("stats should exist");
131 assert_eq!(stats.total_changes, 5);
132 }
133 #[test]
134 pub(super) fn test_analysis_cache() {
135 let mut cache = OCAnalysisCache::new(10);
136 cache.insert("key1".to_string(), vec![1, 2, 3]);
137 assert!(cache.get("key1").is_some());
138 assert!(cache.get("key2").is_none());
139 assert!((cache.hit_rate() - 0.5).abs() < 0.01);
140 cache.invalidate("key1");
141 assert!(!cache.entries["key1"].valid);
142 assert_eq!(cache.size(), 1);
143 }
144 #[test]
145 pub(super) fn test_worklist() {
146 let mut wl = OCWorklist::new();
147 assert!(wl.push(1));
148 assert!(wl.push(2));
149 assert!(!wl.push(1));
150 assert_eq!(wl.len(), 2);
151 assert_eq!(wl.pop(), Some(1));
152 assert!(!wl.contains(1));
153 assert!(wl.contains(2));
154 }
155 #[test]
156 pub(super) fn test_dominator_tree() {
157 let mut dt = OCDominatorTree::new(5);
158 dt.set_idom(1, 0);
159 dt.set_idom(2, 0);
160 dt.set_idom(3, 1);
161 assert!(dt.dominates(0, 3));
162 assert!(dt.dominates(1, 3));
163 assert!(!dt.dominates(2, 3));
164 assert!(dt.dominates(3, 3));
165 }
166 #[test]
167 pub(super) fn test_liveness() {
168 let mut liveness = OCLivenessInfo::new(3);
169 liveness.add_def(0, 1);
170 liveness.add_use(1, 1);
171 assert!(liveness.defs[0].contains(&1));
172 assert!(liveness.uses[1].contains(&1));
173 }
174 #[test]
175 pub(super) fn test_constant_folding() {
176 assert_eq!(OCConstantFoldingHelper::fold_add_i64(3, 4), Some(7));
177 assert_eq!(OCConstantFoldingHelper::fold_div_i64(10, 0), None);
178 assert_eq!(OCConstantFoldingHelper::fold_div_i64(10, 2), Some(5));
179 assert_eq!(
180 OCConstantFoldingHelper::fold_bitand_i64(0b1100, 0b1010),
181 0b1000
182 );
183 assert_eq!(OCConstantFoldingHelper::fold_bitnot_i64(0), -1);
184 }
185 #[test]
186 pub(super) fn test_dep_graph() {
187 let mut g = OCDepGraph::new();
188 g.add_dep(1, 2);
189 g.add_dep(2, 3);
190 g.add_dep(1, 3);
191 assert_eq!(g.dependencies_of(2), vec![1]);
192 let topo = g.topological_sort();
193 assert_eq!(topo.len(), 3);
194 assert!(!g.has_cycle());
195 let pos: std::collections::HashMap<u32, usize> =
196 topo.iter().enumerate().map(|(i, &n)| (n, i)).collect();
197 assert!(pos[&1] < pos[&2]);
198 assert!(pos[&1] < pos[&3]);
199 assert!(pos[&2] < pos[&3]);
200 }
201}
202#[cfg(test)]
203mod ocacheext_pass_tests {
204 use super::*;
205 #[test]
206 pub(super) fn test_ocacheext_phase_order() {
207 assert_eq!(OCacheExtPassPhase::Early.order(), 0);
208 assert_eq!(OCacheExtPassPhase::Middle.order(), 1);
209 assert_eq!(OCacheExtPassPhase::Late.order(), 2);
210 assert_eq!(OCacheExtPassPhase::Finalize.order(), 3);
211 assert!(OCacheExtPassPhase::Early.is_early());
212 assert!(!OCacheExtPassPhase::Early.is_late());
213 }
214 #[test]
215 pub(super) fn test_ocacheext_config_builder() {
216 let c = OCacheExtPassConfig::new("p")
217 .with_phase(OCacheExtPassPhase::Late)
218 .with_max_iter(50)
219 .with_debug(1);
220 assert_eq!(c.name, "p");
221 assert_eq!(c.max_iterations, 50);
222 assert!(c.is_debug_enabled());
223 assert!(c.enabled);
224 let c2 = c.disabled();
225 assert!(!c2.enabled);
226 }
227 #[test]
228 pub(super) fn test_ocacheext_stats() {
229 let mut s = OCacheExtPassStats::new();
230 s.visit();
231 s.visit();
232 s.modify();
233 s.iterate();
234 assert_eq!(s.nodes_visited, 2);
235 assert_eq!(s.nodes_modified, 1);
236 assert!(s.changed);
237 assert_eq!(s.iterations, 1);
238 let e = s.efficiency();
239 assert!((e - 0.5).abs() < 1e-9);
240 }
241 #[test]
242 pub(super) fn test_ocacheext_registry() {
243 let mut r = OCacheExtPassRegistry::new();
244 r.register(OCacheExtPassConfig::new("a").with_phase(OCacheExtPassPhase::Early));
245 r.register(OCacheExtPassConfig::new("b").disabled());
246 assert_eq!(r.len(), 2);
247 assert_eq!(r.enabled_passes().len(), 1);
248 assert_eq!(r.passes_in_phase(&OCacheExtPassPhase::Early).len(), 1);
249 }
250 #[test]
251 pub(super) fn test_ocacheext_cache() {
252 let mut c = OCacheExtCache::new(4);
253 assert!(c.get(99).is_none());
254 c.put(99, vec![1, 2, 3]);
255 let v = c.get(99).expect("v should be present in map");
256 assert_eq!(v, &[1u8, 2, 3]);
257 assert!(c.hit_rate() > 0.0);
258 assert_eq!(c.live_count(), 1);
259 }
260 #[test]
261 pub(super) fn test_ocacheext_worklist() {
262 let mut w = OCacheExtWorklist::new(10);
263 w.push(5);
264 w.push(3);
265 w.push(5);
266 assert_eq!(w.len(), 2);
267 assert!(w.contains(5));
268 let first = w.pop().expect("first should be available to pop");
269 assert!(!w.contains(first));
270 }
271 #[test]
272 pub(super) fn test_ocacheext_dom_tree() {
273 let mut dt = OCacheExtDomTree::new(5);
274 dt.set_idom(1, 0);
275 dt.set_idom(2, 0);
276 dt.set_idom(3, 1);
277 dt.set_idom(4, 1);
278 assert!(dt.dominates(0, 3));
279 assert!(dt.dominates(1, 4));
280 assert!(!dt.dominates(2, 3));
281 assert_eq!(dt.depth_of(3), 2);
282 }
283 #[test]
284 pub(super) fn test_ocacheext_liveness() {
285 let mut lv = OCacheExtLiveness::new(3);
286 lv.add_def(0, 1);
287 lv.add_use(1, 1);
288 assert!(lv.var_is_def_in_block(0, 1));
289 assert!(lv.var_is_used_in_block(1, 1));
290 assert!(!lv.var_is_def_in_block(1, 1));
291 }
292 #[test]
293 pub(super) fn test_ocacheext_const_folder() {
294 let mut cf = OCacheExtConstFolder::new();
295 assert_eq!(cf.add_i64(3, 4), Some(7));
296 assert_eq!(cf.div_i64(10, 0), None);
297 assert_eq!(cf.mul_i64(6, 7), Some(42));
298 assert_eq!(cf.and_i64(0b1100, 0b1010), 0b1000);
299 assert_eq!(cf.fold_count(), 3);
300 assert_eq!(cf.failure_count(), 1);
301 }
302 #[test]
303 pub(super) fn test_ocacheext_dep_graph() {
304 let mut g = OCacheExtDepGraph::new(4);
305 g.add_edge(0, 1);
306 g.add_edge(1, 2);
307 g.add_edge(2, 3);
308 assert!(!g.has_cycle());
309 assert_eq!(g.topo_sort(), Some(vec![0, 1, 2, 3]));
310 assert_eq!(g.reachable(0).len(), 4);
311 let sccs = g.scc();
312 assert_eq!(sccs.len(), 4);
313 }
314}
315#[cfg(test)]
316mod ocachex2_pass_tests {
317 use super::*;
318 #[test]
319 pub(super) fn test_ocachex2_phase_order() {
320 assert_eq!(OCacheX2PassPhase::Early.order(), 0);
321 assert_eq!(OCacheX2PassPhase::Middle.order(), 1);
322 assert_eq!(OCacheX2PassPhase::Late.order(), 2);
323 assert_eq!(OCacheX2PassPhase::Finalize.order(), 3);
324 assert!(OCacheX2PassPhase::Early.is_early());
325 assert!(!OCacheX2PassPhase::Early.is_late());
326 }
327 #[test]
328 pub(super) fn test_ocachex2_config_builder() {
329 let c = OCacheX2PassConfig::new("p")
330 .with_phase(OCacheX2PassPhase::Late)
331 .with_max_iter(50)
332 .with_debug(1);
333 assert_eq!(c.name, "p");
334 assert_eq!(c.max_iterations, 50);
335 assert!(c.is_debug_enabled());
336 assert!(c.enabled);
337 let c2 = c.disabled();
338 assert!(!c2.enabled);
339 }
340 #[test]
341 pub(super) fn test_ocachex2_stats() {
342 let mut s = OCacheX2PassStats::new();
343 s.visit();
344 s.visit();
345 s.modify();
346 s.iterate();
347 assert_eq!(s.nodes_visited, 2);
348 assert_eq!(s.nodes_modified, 1);
349 assert!(s.changed);
350 assert_eq!(s.iterations, 1);
351 let e = s.efficiency();
352 assert!((e - 0.5).abs() < 1e-9);
353 }
354 #[test]
355 pub(super) fn test_ocachex2_registry() {
356 let mut r = OCacheX2PassRegistry::new();
357 r.register(OCacheX2PassConfig::new("a").with_phase(OCacheX2PassPhase::Early));
358 r.register(OCacheX2PassConfig::new("b").disabled());
359 assert_eq!(r.len(), 2);
360 assert_eq!(r.enabled_passes().len(), 1);
361 assert_eq!(r.passes_in_phase(&OCacheX2PassPhase::Early).len(), 1);
362 }
363 #[test]
364 pub(super) fn test_ocachex2_cache() {
365 let mut c = OCacheX2Cache::new(4);
366 assert!(c.get(99).is_none());
367 c.put(99, vec![1, 2, 3]);
368 let v = c.get(99).expect("v should be present in map");
369 assert_eq!(v, &[1u8, 2, 3]);
370 assert!(c.hit_rate() > 0.0);
371 assert_eq!(c.live_count(), 1);
372 }
373 #[test]
374 pub(super) fn test_ocachex2_worklist() {
375 let mut w = OCacheX2Worklist::new(10);
376 w.push(5);
377 w.push(3);
378 w.push(5);
379 assert_eq!(w.len(), 2);
380 assert!(w.contains(5));
381 let first = w.pop().expect("first should be available to pop");
382 assert!(!w.contains(first));
383 }
384 #[test]
385 pub(super) fn test_ocachex2_dom_tree() {
386 let mut dt = OCacheX2DomTree::new(5);
387 dt.set_idom(1, 0);
388 dt.set_idom(2, 0);
389 dt.set_idom(3, 1);
390 dt.set_idom(4, 1);
391 assert!(dt.dominates(0, 3));
392 assert!(dt.dominates(1, 4));
393 assert!(!dt.dominates(2, 3));
394 assert_eq!(dt.depth_of(3), 2);
395 }
396 #[test]
397 pub(super) fn test_ocachex2_liveness() {
398 let mut lv = OCacheX2Liveness::new(3);
399 lv.add_def(0, 1);
400 lv.add_use(1, 1);
401 assert!(lv.var_is_def_in_block(0, 1));
402 assert!(lv.var_is_used_in_block(1, 1));
403 assert!(!lv.var_is_def_in_block(1, 1));
404 }
405 #[test]
406 pub(super) fn test_ocachex2_const_folder() {
407 let mut cf = OCacheX2ConstFolder::new();
408 assert_eq!(cf.add_i64(3, 4), Some(7));
409 assert_eq!(cf.div_i64(10, 0), None);
410 assert_eq!(cf.mul_i64(6, 7), Some(42));
411 assert_eq!(cf.and_i64(0b1100, 0b1010), 0b1000);
412 assert_eq!(cf.fold_count(), 3);
413 assert_eq!(cf.failure_count(), 1);
414 }
415 #[test]
416 pub(super) fn test_ocachex2_dep_graph() {
417 let mut g = OCacheX2DepGraph::new(4);
418 g.add_edge(0, 1);
419 g.add_edge(1, 2);
420 g.add_edge(2, 3);
421 assert!(!g.has_cycle());
422 assert_eq!(g.topo_sort(), Some(vec![0, 1, 2, 3]));
423 assert_eq!(g.reachable(0).len(), 4);
424 let sccs = g.scc();
425 assert_eq!(sccs.len(), 4);
426 }
427}