Beyond Relooper: Recursive Translation of Unstructured Control Flow to Structu…
summary
Translates arbitrary intraprocedural control-flow graphs into structured WebAssembly constructs and reduces the classic three-pass Peterson/Kasami/Tokura method to a single-pass translation by replacing side-effect emissions with a recursive function that returns immutable ASTs. Uses reverse-postorder numbering and a dominator tree to decide loop wrappers, if-ends, and multilevel breaks; handles reducible graphs (irreducible ones require prior transformation). Implementation is slated for Glasgow Haskell Compiler and has evaluated artifacts available.
AI-written summary · about
chapters (5)
- 0:00Start
- 2:43Not all control flow is structured
- 6:46Code shape determined by graph properties
- 7:30Code placement determined by dominance
- 10:38Recursion over dominator tree
related talks
44mLet's talk about transpilers
01h 05mControl Flow Obfuscation for Featherweight Java + Efficient Fair Conjunction
17mEfficient Bottom-Up Synthesis for Programs with Local Variables
27mDistributing and Parallelizing Non-canonical Loops
15mLightweight On-Stack Replacement in Languages with Unstructured Loops
23mAn Abstract Interpretation for SPMD Divergence on Reducible Control Flow Graphs
24mA Big-Step Compositional Continuation-Passing Semantics for WebAssembly
28mCombinator-Based Fixpoint Algorithms for Big-Step Abstract Interpreters