Part of #9. Phase 3 — native dataflow.
Learning goals
Classic graph algorithms in idiomatic Rust: the Cooper–Harper–Kennedy iterative dominator
algorithm (~40 lines — resist Lengauer–Tarjan until profiling demands it), reverse-graph
post-dominators, bitset worklists (fixedbitset), and writing algorithm code that borrows from
an arena without fighting the checker.
Task
- Dominators, and post-dominators on the reverse CFG (CHK iterative, both directions from one
implementation parameterized over edge direction — a nice generics exercise).
- Infinite loops (
loop {} with no break) break post-dominance: add the synthetic edge from a
documented loop node to EXIT first.
- Control dependence via Ferrante–Ottenstein–Warren: for each CFG edge (a, b) where b does not
post-dominate a, walk b up the post-dominator tree to (excluding) a's post-dominator, marking
each visited node control-dependent on a. These are your CDG edges.
Gate (dominance gate)
- Post-dominator tree is a tree rooted at EXIT (asserted structurally).
- Hand-computed control dependences for the fixture's if/loop/early-return/
? functions match
EXACTLY — write the expected sets down before running the code.
Part of #9. Phase 3 — native dataflow.
Learning goals
Classic graph algorithms in idiomatic Rust: the Cooper–Harper–Kennedy iterative dominator
algorithm (~40 lines — resist Lengauer–Tarjan until profiling demands it), reverse-graph
post-dominators, bitset worklists (
fixedbitset), and writing algorithm code that borrows froman arena without fighting the checker.
Task
implementation parameterized over edge direction — a nice generics exercise).
loop {}with no break) break post-dominance: add the synthetic edge from adocumented loop node to EXIT first.
post-dominate a, walk b up the post-dominator tree to (excluding) a's post-dominator, marking
each visited node control-dependent on a. These are your CDG edges.
Gate (dominance gate)
?functions matchEXACTLY — write the expected sets down before running the code.