1use std::collections::{HashMap, HashSet};
6
7use super::types::{
8 AllocationSinkKind, ConnectionGraph, EscapeAnnotation, EscapeAnnotationPass,
9 EscapeBasedRefCountOpt, EscapeEdgeKind, EscapeFlowGraph2, EscapeOptimizationPass,
10 EscapeOptimizationResult, EscapeSummary, FieldEscapeInfo, InterproceduralEscapeAnalysis,
11 OEAnalysisCache, OEConstantFoldingHelper, OEDepGraph, OEDominatorTree, OEExtCache,
12 OEExtConstFolder, OEExtDepGraph, OEExtDomTree, OEExtLiveness, OEExtPassConfig, OEExtPassPhase,
13 OEExtPassRegistry, OEExtPassStats, OEExtWorklist, OELivenessInfo, OEPassConfig, OEPassPhase,
14 OEPassRegistry, OEPassStats, OEWorklist, OEX2Cache, OEX2ConstFolder, OEX2DepGraph, OEX2DomTree,
15 OEX2Liveness, OEX2PassConfig, OEX2PassPhase, OEX2PassRegistry, OEX2PassStats, OEX2Worklist,
16 PointsToSet2, PointsToTarget, StructFieldEscapeAnalyzer,
17};
18
19#[cfg(test)]
20mod opt_escape_extended_tests {
21 use super::*;
22 #[test]
23 pub(super) fn test_points_to_set() {
24 let mut pts = PointsToSet2::new();
25 pts.add(PointsToTarget::HeapObject(1));
26 pts.add(PointsToTarget::HeapObject(2));
27 assert_eq!(pts.len(), 2);
28 let mut pts2 = PointsToSet2::new();
29 pts2.add(PointsToTarget::HeapObject(2));
30 assert!(pts.may_alias(&pts2));
31 let pts3 = PointsToSet2::new();
32 assert!(!pts.may_alias(&pts3));
33 }
34 #[test]
35 pub(super) fn test_escape_flow_graph() {
36 let mut g = EscapeFlowGraph2::new();
37 g.add_node(1);
38 g.add_node(2);
39 g.add_edge(1, 2, EscapeEdgeKind::DirectAssign);
40 g.add_edge(2, 3, EscapeEdgeKind::Return);
41 assert_eq!(g.node_count(), 3);
42 assert_eq!(g.edge_count(), 2);
43 assert_eq!(g.successors(1), vec![2]);
44 assert_eq!(g.predecessors(2), vec![1]);
45 }
46 #[test]
47 pub(super) fn test_allocation_sink_kind() {
48 assert!(AllocationSinkKind::Stack.is_stack_eligible());
49 assert!(AllocationSinkKind::ArenaAllocated.is_stack_eligible());
50 assert!(!AllocationSinkKind::HeapLongLived.is_stack_eligible());
51 }
52 #[test]
53 pub(super) fn test_optimization_result() {
54 let result =
55 EscapeOptimizationResult::new(42, AllocationSinkKind::Stack, "no escape detected")
56 .with_confidence(0.95);
57 assert!(result.is_high_confidence());
58 assert_eq!(result.allocation_id, 42);
59 }
60 #[test]
61 pub(super) fn test_escape_opt_pass() {
62 let mut pass = EscapeOptimizationPass::new();
63 pass.add_result(
64 EscapeOptimizationResult::new(1, AllocationSinkKind::Stack, "short-lived")
65 .with_confidence(0.95),
66 );
67 pass.add_result(
68 EscapeOptimizationResult::new(2, AllocationSinkKind::HeapLongLived, "long-lived")
69 .with_confidence(0.6),
70 );
71 assert_eq!(pass.total_optimizations(), 2);
72 let promotable = pass.stack_promotable();
73 assert_eq!(promotable.len(), 1);
74 let report = pass.emit_report();
75 assert!(report.contains("Stack-promotable allocations: 1"));
76 }
77 #[test]
78 pub(super) fn test_struct_field_escape() {
79 let mut analyzer = StructFieldEscapeAnalyzer::new();
80 analyzer.add_field(FieldEscapeInfo::new("Foo", "x"));
81 let mut f2 = FieldEscapeInfo::new("Foo", "y");
82 f2.escapes_via_return = true;
83 analyzer.add_field(f2);
84 assert_eq!(analyzer.escaping_fields().len(), 1);
85 assert_eq!(analyzer.non_escaping_fields().len(), 1);
86 assert!(!analyzer.can_scalar_replace_struct("Foo"));
87 }
88 #[test]
89 pub(super) fn test_connection_graph() {
90 let mut cg = ConnectionGraph::new();
91 cg.add_node(1, "allocation");
92 cg.add_node(2, "local_var");
93 cg.add_deferred_edge(1, 2);
94 cg.propagate_escape();
95 let non_escaping = cg.non_escaping_allocations();
96 assert_eq!(non_escaping.len(), 2);
97 }
98 #[test]
99 pub(super) fn test_interprocedural_escape() {
100 let mut ipa = InterproceduralEscapeAnalysis::new();
101 let mut summary = EscapeSummary::default();
102 summary.escaping_params.push(0);
103 ipa.register_summary("foo", summary);
104 assert!(ipa.param_escapes("foo", 0));
105 assert!(!ipa.param_escapes("foo", 1));
106 assert!(ipa.param_escapes("unknown", 0));
107 }
108 #[test]
109 pub(super) fn test_refcount_opt() {
110 let mut opt = EscapeBasedRefCountOpt::new();
111 opt.record_elimination();
112 opt.record_elimination();
113 opt.record_stack_replace(10);
114 assert_eq!(opt.total_eliminated(), 4);
115 let report = opt.savings_report();
116 assert!(report.contains("2 retain/release pairs"));
117 assert!(report.contains("1 stack promotions"));
118 }
119 #[test]
120 pub(super) fn test_annotation_pass() {
121 let mut pass = EscapeAnnotationPass::new();
122 pass.annotate(1, EscapeAnnotation::StackAlloc);
123 pass.annotate(2, EscapeAnnotation::HeapAlloc);
124 let candidates = pass.stack_promote_candidates();
125 assert_eq!(candidates, vec![1]);
126 assert!(matches!(
127 pass.get_annotation(2),
128 Some(EscapeAnnotation::HeapAlloc)
129 ));
130 }
131}
132#[cfg(test)]
133mod OE_infra_tests {
134 use super::*;
135 #[test]
136 pub(super) fn test_pass_config() {
137 let config = OEPassConfig::new("test_pass", OEPassPhase::Transformation);
138 assert!(config.enabled);
139 assert!(config.phase.is_modifying());
140 assert_eq!(config.phase.name(), "transformation");
141 }
142 #[test]
143 pub(super) fn test_pass_stats() {
144 let mut stats = OEPassStats::new();
145 stats.record_run(10, 100, 3);
146 stats.record_run(20, 200, 5);
147 assert_eq!(stats.total_runs, 2);
148 assert!((stats.average_changes_per_run() - 15.0).abs() < 0.01);
149 assert!((stats.success_rate() - 1.0).abs() < 0.01);
150 let s = stats.format_summary();
151 assert!(s.contains("Runs: 2/2"));
152 }
153 #[test]
154 pub(super) fn test_pass_registry() {
155 let mut reg = OEPassRegistry::new();
156 reg.register(OEPassConfig::new("pass_a", OEPassPhase::Analysis));
157 reg.register(OEPassConfig::new("pass_b", OEPassPhase::Transformation).disabled());
158 assert_eq!(reg.total_passes(), 2);
159 assert_eq!(reg.enabled_count(), 1);
160 reg.update_stats("pass_a", 5, 50, 2);
161 let stats = reg.get_stats("pass_a").expect("stats should exist");
162 assert_eq!(stats.total_changes, 5);
163 }
164 #[test]
165 pub(super) fn test_analysis_cache() {
166 let mut cache = OEAnalysisCache::new(10);
167 cache.insert("key1".to_string(), vec![1, 2, 3]);
168 assert!(cache.get("key1").is_some());
169 assert!(cache.get("key2").is_none());
170 assert!((cache.hit_rate() - 0.5).abs() < 0.01);
171 cache.invalidate("key1");
172 assert!(!cache.entries["key1"].valid);
173 assert_eq!(cache.size(), 1);
174 }
175 #[test]
176 pub(super) fn test_worklist() {
177 let mut wl = OEWorklist::new();
178 assert!(wl.push(1));
179 assert!(wl.push(2));
180 assert!(!wl.push(1));
181 assert_eq!(wl.len(), 2);
182 assert_eq!(wl.pop(), Some(1));
183 assert!(!wl.contains(1));
184 assert!(wl.contains(2));
185 }
186 #[test]
187 pub(super) fn test_dominator_tree() {
188 let mut dt = OEDominatorTree::new(5);
189 dt.set_idom(1, 0);
190 dt.set_idom(2, 0);
191 dt.set_idom(3, 1);
192 assert!(dt.dominates(0, 3));
193 assert!(dt.dominates(1, 3));
194 assert!(!dt.dominates(2, 3));
195 assert!(dt.dominates(3, 3));
196 }
197 #[test]
198 pub(super) fn test_liveness() {
199 let mut liveness = OELivenessInfo::new(3);
200 liveness.add_def(0, 1);
201 liveness.add_use(1, 1);
202 assert!(liveness.defs[0].contains(&1));
203 assert!(liveness.uses[1].contains(&1));
204 }
205 #[test]
206 pub(super) fn test_constant_folding() {
207 assert_eq!(OEConstantFoldingHelper::fold_add_i64(3, 4), Some(7));
208 assert_eq!(OEConstantFoldingHelper::fold_div_i64(10, 0), None);
209 assert_eq!(OEConstantFoldingHelper::fold_div_i64(10, 2), Some(5));
210 assert_eq!(
211 OEConstantFoldingHelper::fold_bitand_i64(0b1100, 0b1010),
212 0b1000
213 );
214 assert_eq!(OEConstantFoldingHelper::fold_bitnot_i64(0), -1);
215 }
216 #[test]
217 pub(super) fn test_dep_graph() {
218 let mut g = OEDepGraph::new();
219 g.add_dep(1, 2);
220 g.add_dep(2, 3);
221 g.add_dep(1, 3);
222 assert_eq!(g.dependencies_of(2), vec![1]);
223 let topo = g.topological_sort();
224 assert_eq!(topo.len(), 3);
225 assert!(!g.has_cycle());
226 let pos: std::collections::HashMap<u32, usize> =
227 topo.iter().enumerate().map(|(i, &n)| (n, i)).collect();
228 assert!(pos[&1] < pos[&2]);
229 assert!(pos[&1] < pos[&3]);
230 assert!(pos[&2] < pos[&3]);
231 }
232}
233#[cfg(test)]
234mod oeext_pass_tests {
235 use super::*;
236 #[test]
237 pub(super) fn test_oeext_phase_order() {
238 assert_eq!(OEExtPassPhase::Early.order(), 0);
239 assert_eq!(OEExtPassPhase::Middle.order(), 1);
240 assert_eq!(OEExtPassPhase::Late.order(), 2);
241 assert_eq!(OEExtPassPhase::Finalize.order(), 3);
242 assert!(OEExtPassPhase::Early.is_early());
243 assert!(!OEExtPassPhase::Early.is_late());
244 }
245 #[test]
246 pub(super) fn test_oeext_config_builder() {
247 let c = OEExtPassConfig::new("p")
248 .with_phase(OEExtPassPhase::Late)
249 .with_max_iter(50)
250 .with_debug(1);
251 assert_eq!(c.name, "p");
252 assert_eq!(c.max_iterations, 50);
253 assert!(c.is_debug_enabled());
254 assert!(c.enabled);
255 let c2 = c.disabled();
256 assert!(!c2.enabled);
257 }
258 #[test]
259 pub(super) fn test_oeext_stats() {
260 let mut s = OEExtPassStats::new();
261 s.visit();
262 s.visit();
263 s.modify();
264 s.iterate();
265 assert_eq!(s.nodes_visited, 2);
266 assert_eq!(s.nodes_modified, 1);
267 assert!(s.changed);
268 assert_eq!(s.iterations, 1);
269 let e = s.efficiency();
270 assert!((e - 0.5).abs() < 1e-9);
271 }
272 #[test]
273 pub(super) fn test_oeext_registry() {
274 let mut r = OEExtPassRegistry::new();
275 r.register(OEExtPassConfig::new("a").with_phase(OEExtPassPhase::Early));
276 r.register(OEExtPassConfig::new("b").disabled());
277 assert_eq!(r.len(), 2);
278 assert_eq!(r.enabled_passes().len(), 1);
279 assert_eq!(r.passes_in_phase(&OEExtPassPhase::Early).len(), 1);
280 }
281 #[test]
282 pub(super) fn test_oeext_cache() {
283 let mut c = OEExtCache::new(4);
284 assert!(c.get(99).is_none());
285 c.put(99, vec![1, 2, 3]);
286 let v = c.get(99).expect("v should be present in map");
287 assert_eq!(v, &[1u8, 2, 3]);
288 assert!(c.hit_rate() > 0.0);
289 assert_eq!(c.live_count(), 1);
290 }
291 #[test]
292 pub(super) fn test_oeext_worklist() {
293 let mut w = OEExtWorklist::new(10);
294 w.push(5);
295 w.push(3);
296 w.push(5);
297 assert_eq!(w.len(), 2);
298 assert!(w.contains(5));
299 let first = w.pop().expect("first should be available to pop");
300 assert!(!w.contains(first));
301 }
302 #[test]
303 pub(super) fn test_oeext_dom_tree() {
304 let mut dt = OEExtDomTree::new(5);
305 dt.set_idom(1, 0);
306 dt.set_idom(2, 0);
307 dt.set_idom(3, 1);
308 dt.set_idom(4, 1);
309 assert!(dt.dominates(0, 3));
310 assert!(dt.dominates(1, 4));
311 assert!(!dt.dominates(2, 3));
312 assert_eq!(dt.depth_of(3), 2);
313 }
314 #[test]
315 pub(super) fn test_oeext_liveness() {
316 let mut lv = OEExtLiveness::new(3);
317 lv.add_def(0, 1);
318 lv.add_use(1, 1);
319 assert!(lv.var_is_def_in_block(0, 1));
320 assert!(lv.var_is_used_in_block(1, 1));
321 assert!(!lv.var_is_def_in_block(1, 1));
322 }
323 #[test]
324 pub(super) fn test_oeext_const_folder() {
325 let mut cf = OEExtConstFolder::new();
326 assert_eq!(cf.add_i64(3, 4), Some(7));
327 assert_eq!(cf.div_i64(10, 0), None);
328 assert_eq!(cf.mul_i64(6, 7), Some(42));
329 assert_eq!(cf.and_i64(0b1100, 0b1010), 0b1000);
330 assert_eq!(cf.fold_count(), 3);
331 assert_eq!(cf.failure_count(), 1);
332 }
333 #[test]
334 pub(super) fn test_oeext_dep_graph() {
335 let mut g = OEExtDepGraph::new(4);
336 g.add_edge(0, 1);
337 g.add_edge(1, 2);
338 g.add_edge(2, 3);
339 assert!(!g.has_cycle());
340 assert_eq!(g.topo_sort(), Some(vec![0, 1, 2, 3]));
341 assert_eq!(g.reachable(0).len(), 4);
342 let sccs = g.scc();
343 assert_eq!(sccs.len(), 4);
344 }
345}
346#[cfg(test)]
347mod oex2_pass_tests {
348 use super::*;
349 #[test]
350 pub(super) fn test_oex2_phase_order() {
351 assert_eq!(OEX2PassPhase::Early.order(), 0);
352 assert_eq!(OEX2PassPhase::Middle.order(), 1);
353 assert_eq!(OEX2PassPhase::Late.order(), 2);
354 assert_eq!(OEX2PassPhase::Finalize.order(), 3);
355 assert!(OEX2PassPhase::Early.is_early());
356 assert!(!OEX2PassPhase::Early.is_late());
357 }
358 #[test]
359 pub(super) fn test_oex2_config_builder() {
360 let c = OEX2PassConfig::new("p")
361 .with_phase(OEX2PassPhase::Late)
362 .with_max_iter(50)
363 .with_debug(1);
364 assert_eq!(c.name, "p");
365 assert_eq!(c.max_iterations, 50);
366 assert!(c.is_debug_enabled());
367 assert!(c.enabled);
368 let c2 = c.disabled();
369 assert!(!c2.enabled);
370 }
371 #[test]
372 pub(super) fn test_oex2_stats() {
373 let mut s = OEX2PassStats::new();
374 s.visit();
375 s.visit();
376 s.modify();
377 s.iterate();
378 assert_eq!(s.nodes_visited, 2);
379 assert_eq!(s.nodes_modified, 1);
380 assert!(s.changed);
381 assert_eq!(s.iterations, 1);
382 let e = s.efficiency();
383 assert!((e - 0.5).abs() < 1e-9);
384 }
385 #[test]
386 pub(super) fn test_oex2_registry() {
387 let mut r = OEX2PassRegistry::new();
388 r.register(OEX2PassConfig::new("a").with_phase(OEX2PassPhase::Early));
389 r.register(OEX2PassConfig::new("b").disabled());
390 assert_eq!(r.len(), 2);
391 assert_eq!(r.enabled_passes().len(), 1);
392 assert_eq!(r.passes_in_phase(&OEX2PassPhase::Early).len(), 1);
393 }
394 #[test]
395 pub(super) fn test_oex2_cache() {
396 let mut c = OEX2Cache::new(4);
397 assert!(c.get(99).is_none());
398 c.put(99, vec![1, 2, 3]);
399 let v = c.get(99).expect("v should be present in map");
400 assert_eq!(v, &[1u8, 2, 3]);
401 assert!(c.hit_rate() > 0.0);
402 assert_eq!(c.live_count(), 1);
403 }
404 #[test]
405 pub(super) fn test_oex2_worklist() {
406 let mut w = OEX2Worklist::new(10);
407 w.push(5);
408 w.push(3);
409 w.push(5);
410 assert_eq!(w.len(), 2);
411 assert!(w.contains(5));
412 let first = w.pop().expect("first should be available to pop");
413 assert!(!w.contains(first));
414 }
415 #[test]
416 pub(super) fn test_oex2_dom_tree() {
417 let mut dt = OEX2DomTree::new(5);
418 dt.set_idom(1, 0);
419 dt.set_idom(2, 0);
420 dt.set_idom(3, 1);
421 dt.set_idom(4, 1);
422 assert!(dt.dominates(0, 3));
423 assert!(dt.dominates(1, 4));
424 assert!(!dt.dominates(2, 3));
425 assert_eq!(dt.depth_of(3), 2);
426 }
427 #[test]
428 pub(super) fn test_oex2_liveness() {
429 let mut lv = OEX2Liveness::new(3);
430 lv.add_def(0, 1);
431 lv.add_use(1, 1);
432 assert!(lv.var_is_def_in_block(0, 1));
433 assert!(lv.var_is_used_in_block(1, 1));
434 assert!(!lv.var_is_def_in_block(1, 1));
435 }
436 #[test]
437 pub(super) fn test_oex2_const_folder() {
438 let mut cf = OEX2ConstFolder::new();
439 assert_eq!(cf.add_i64(3, 4), Some(7));
440 assert_eq!(cf.div_i64(10, 0), None);
441 assert_eq!(cf.mul_i64(6, 7), Some(42));
442 assert_eq!(cf.and_i64(0b1100, 0b1010), 0b1000);
443 assert_eq!(cf.fold_count(), 3);
444 assert_eq!(cf.failure_count(), 1);
445 }
446 #[test]
447 pub(super) fn test_oex2_dep_graph() {
448 let mut g = OEX2DepGraph::new(4);
449 g.add_edge(0, 1);
450 g.add_edge(1, 2);
451 g.add_edge(2, 3);
452 assert!(!g.has_cycle());
453 assert_eq!(g.topo_sort(), Some(vec![0, 1, 2, 3]));
454 assert_eq!(g.reachable(0).len(), 4);
455 let sccs = g.scc();
456 assert_eq!(sccs.len(), 4);
457 }
458}