Beyond Relooper: Recursive Translation of Unstructured Control Flow to Structured Control Flow (Functional Pearl)

作     者：Ramsey, Norman 

作者机构：Tweag Paris France Tufts Univ Medford MA 02155 USA 

出 版 物：《PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL》 (Proc. ACM Program. Lang.)

年 卷 期：2022年第6卷第ICFP期

页      面：1–22页

核心收录：

主　　题：WebAssembly control-flow analysis dominator tree reverse postorder numbering Haskell 

摘      要：In many compilers, control flow is represented using an arbitrary directed graph. But in some interesting target languages, including JavaScript and WebAssembly, intraprocedural control flow can be expressed only in structured ways, using loops, conditionals, and multilevel breaks or exits. As was shown by Peterson, Kasami, and Tokura in 1973, such structured control flow can be obtained by translating arbitrary control flow. The translation uses two standard analyses, but as published, it takes three passes-Dwhich may explain why it was overlooked by Emscripten, a popular compiler from C to JavaScript. By tweaking the analyses and by applying fundamental ideas from functional programming (recursive functions and immutable abstract-syntax trees), the translation, along with a couple of code improvements, can be implemented in a single pass. This new implementation is slated to be added to the Glasgow Haskell Compiler. Its single-pass translation, its immutable representation, and its use of dominator trees make it much easier to reason about than the original translation.