<p>I'm writing a transpile for a C-like language to Javascript, which lacks a <code>goto</code> statement. Unfortunately the existing library code contains a lot of <code>goto</code>. How can I translate this?</p>
<p>I need to handle both forward and backwards jumps. Both the source and destination of a jump could be inside a loop or conditional.</p>
<p>Code example showing several possible cases:</p>
<pre class="lang-c prettyprint-override"><code>void main() {
    start: int f = getchar();
    while (f&lt;3) {
        loop:f+=1;
    }
    g = getchar();
    f+=g;
    
    if (g &gt; 5) {
        goto loop;
    } else {
        for (int j=0; j&lt;12; j++) {
            if (j==f) {
                goto start;
            } else if (j==-f) {
                goto end;
            }
        }
    }

    end:
}
</code></pre>

<compilers><control-flow><transpilers>
How to transpile goto to a language that lacks it?
<p>Check out the Relooper algorithm, originally created for the Emscripten C-to-Javascript compiler. It describes a way to compile arbitrary control flow graphs using only if, while, and labelled break statements (those break statements that can break out of an outer loop). Relooper is also used in compilers that target WebAssembly (which also doesn't have goto).</p>
<hr />
<p><strong>Emscripten: an LLVM-to-JavaScript compiler</strong><br />
Alon Zakai (2011) <a href="https://dl.acm.org/doi/10.1145/2048147.2048224" rel="nofollow noreferrer">https://dl.acm.org/doi/10.1145/2048147.2048224</a></p>
<p><strong>Beyond Relooper: recursive translation of unstructured control flow to structured control flow</strong><br />
Norman Ramsey (2022) <a href="https://dl.acm.org/doi/10.1145/3547621" rel="nofollow noreferrer">https://dl.acm.org/doi/10.1145/3547621</a></p>

CC BY-SA 4.0
2023-05-25T00:30:49.580Z
2023-05-25T22:49:43.170Z
2023-05-25T22:49:43.170Z
hugomg
CC BY-SA 4.0
2023-06-30T02:47:07.807Z
I found it hard to follow the Emscripten paper, so I'll have to check out the Beyond Relooper paper to see if it's easier to grasp its concepts!
curiousdannii
<p>Programs with <code>goto</code> can have arbitrary <a href="https://en.wikipedia.org/wiki/Control-flow_graph" rel="noreferrer">control-flow graphs</a> (CFGs), so the goal here is to translate from any CFG into structured control-flow, according to some definition of &quot;structured&quot;. I'll assume that a CFG for the program has already been computed. It's worth mentioning that because this requires a universal solution that works for any CFG, it will work for compiling from <em>any</em> imperative language, though it may be overkill for some purposes.</p>
<p>The classical version of this problem allows for only <code>if</code>/<code>else</code> statements and <code>while</code> loops in the target language. The <a href="https://en.wikipedia.org/wiki/Structured_program_theorem" rel="noreferrer">structured program theorem</a> says that these two control-flow constructs (plus &quot;sequence&quot; ─ following one statement with another) are sufficient to represent any CFG.</p>
<hr />
<p>The easiest-to-explain solution is to build a state machine; Wikipedia calls this the &quot;<a href="https://en.wikipedia.org/wiki/Structured_program_theorem#Single-while-loop,_folk_version_of_the_theorem" rel="noreferrer">folk version of the theorem</a>&quot;. Assign numerical IDs to each node in the CFG, starting from 0 for the entry point. Then the whole program can be translated into this form:</p>
<pre class="lang-javascript prettyprint-override"><code>let state = 0;
while(state &gt;= 0) {
    if(state === 0) {
        // statements from node 0
    }
    else if(state === 1) {
        // statements from node 1
    }
    // ...
}
</code></pre>
<p>To transition from one node to another, simply assign the appropriate ID for the next block (or −1 to terminate the program) to the variable <code>state</code>, using an <code>if</code> statement to branch on the appropriate condition.</p>
<hr />
<p>However, the state machine approach is not great for performance or readability, since the multi-way branch inside the loop is difficult for the <a href="https://en.wikipedia.org/wiki/Branch_predictor" rel="noreferrer">branch predictor</a>. Alternative approaches work by induction on the structure of the CFG, and can produce better quality output code. Additionally, the target language may support more control-flow constructs (e.g. <code>do</code>/<code>while</code> loops, <code>switch</code>, <code>break</code> and <code>continue</code>) allowing further improvements.</p>
<p>There are a few notable solutions in this category designed specifically for compiling CFGs into <a href="https://en.wikipedia.org/wiki/WebAssembly" rel="noreferrer">WebAssembly</a>, which despite otherwise being an assembly language, lacks jumps. WebAssembly's control-flow statements are equivalent to <code>if</code>/<code>else</code> and <code>while</code> loops with labelled <code>break</code> and <code>continue</code>. Existing algorithms which solve this problem for WebAssembly include:</p>
<ul>
<li>Cheerp's Stackifier ─ described in <a href="https://medium.com/leaningtech/solving-the-structured-control-flow-problem-once-and-for-all-5123117b1ee2" rel="noreferrer">this Medium post</a>.</li>
<li>Emscripten's Relooper ─ described in <a href="https://github.com/emscripten-core/emscripten/blob/main/docs/paper.pdf" rel="noreferrer">this paper</a>.</li>
<li>LLVM's WebAssemblyCFGStackify algorithm ─ I can't find a decent explainer, but <a href="https://gitlab.inria.fr/why3/why3/-/merge_requests/453" rel="noreferrer">this</a> seems to be based on it, and <a href="https://gist.github.com/evanw/58a8a5b8b4a1da32fcdcfbf9da87c82a" rel="noreferrer">this</a> claims to be a simplified version.</li>
</ul>
<p>These approaches should also work for compiling to Javascript, since Javascript has all of the control-flow statements that WebAssembly uses.</p>

CC BY-SA 4.0
2023-05-24T20:56:21.053Z
2023-05-25T10:24:26.970Z
2023-05-25T10:24:26.970Z
kaya3
<h1>Finite State Machines</h1>
<p>An <a href="https://en.wikipedia.org/wiki/Finite-state_machine" rel="nofollow noreferrer">FSM</a> is an abstract machine where each step is represented as a state, and where computation is a sequence of state transitions.<br />
Each labelled subroutine is its own state, which you can represent this way:</p>
<pre class="lang-c prettyprint-override"><code>machine main()
{
    int f;
    int g;
    state start
    {
        f = getchar();
        if(f &lt; 3) {
            goto loop;
        }
        else {
            goto start2;
        }
    }
    state loop
    {
        f += 1;
        if(f &lt; 3) {
            goto loop;
        }
        else {
            goto start2;
        }
    }
    state start2
    {
        g = getchar();
        f += g;
        if(g &gt; 5) {
            goto loop;
        }
        else {
            for(int j = 0; j &lt; 12; ++j) {
                if(j == f) {
                    goto start;
                }
                else if(j == -f) {
                    goto end;
                }
            }
        }
    }
    state end {}
}
</code></pre>
<p>In a C-like language, that is <code>while/switch</code>. And you can simplify some loop states using <code>do while</code>. And since you mention JavaScript, here's your example code ported to JS:</p>
<pre class="lang-js prettyprint-override"><code>function main()
{
    let _state = 0;
    let f, g;
    _fsm: while(true) {
        switch(_state) {
        case 0:
            f = getchar();
            if(f &lt; 3) {
                _state = 1;
                continue _fsm;
            }
            else {
                _state = 2;
                continue _fsm;
            }
        case 1:
            do {
                f += 1;
            } while(f &lt; 3);
            _state = 2;
            continue _fsm;
        case 2:
            g = prompt();
            f += g;
            if(g &gt; 5) {
                _state = 1;
                continue _fsm;
            }
            else {
                for(let j = 0; j &lt; 12; ++j) {
                    if(j == f) {
                        _state = 0;
                        continue _fsm;
                    }
                    else if(j == -f) {
                        _state = -1;
                        continue _fsm;
                    }
                }
            }
        case -1:
            break _fsm;
        }
    }
}
</code></pre>

CC BY-SA 4.0
2023-05-24T20:45:04.843Z
2023-05-26T09:27:02.020Z
2023-05-26T09:27:02.020Z
Longinus
# How to transpile goto to a language that lacks it?
Posted by: username_0 on 2023-05-24
I'm writing a transpile for a C-like language to Javascript, which lacks a goto statement. Unfortunately the existing library code contains a lot of goto. How can I translate this?
I need to handle both forward and backwards jumps. Both the source and destination of a jump could be inside a loop or conditional.
Code example showing several possible cases:
void main() {
    start: int f = getchar();
    while (f<3) {
        loop:f+=1;
    }
    g = getchar();
    f+=g;
    
    if (g > 5) {
        goto loop;
    } else {
        for (int j=0; j<12; j++) {
            if (j==f) {
                goto start;
            } else if (j==-f) {
                goto end;
            }
        }
    }

    end:
}
**Tags:** compilers control-flow transpilers
---
## 3 answers
### Answer by username_3 on 2023-05-24. Score: 17
Programs with goto can have arbitrary control-flow graphs (CFGs), so the goal here is to translate from any CFG into structured control-flow, according to some definition of "structured". I'll assume that a CFG for the program has already been computed. It's worth mentioning that because this requires a universal solution that works for any CFG, it will work for compiling from any imperative language, though it may be overkill for some purposes.
The classical version of this problem allows for only if/else statements and while loops in the target language. The structured program theorem says that these two control-flow constructs (plus "sequence" ─ following one statement with another) are sufficient to represent any CFG.

The easiest-to-explain solution is to build a state machine; Wikipedia calls this the "folk version of the theorem". Assign numerical IDs to each node in the CFG, starting from 0 for the entry point. Then the whole program can be translated into this form:
let state = 0;
while(state >= 0) {
    if(state === 0) {
        // statements from node 0
    }
    else if(state === 1) {
        // statements from node 1
    }
    // ...
}

To transition from one node to another, simply assign the appropriate ID for the next block (or −1 to terminate the program) to the variable state, using an if statement to branch on the appropriate condition.

However, the state machine approach is not great for performance or readability, since the multi-way branch inside the loop is difficult for the branch predictor. Alternative approaches work by induction on the structure of the CFG, and can produce better quality output code. Additionally, the target language may support more control-flow constructs (e.g. do/while loops, switch, break and continue) allowing further improvements.
There are a few notable solutions in this category designed specifically for compiling CFGs into WebAssembly, which despite otherwise being an assembly language, lacks jumps. WebAssembly's control-flow statements are equivalent to if/else and while loops with labelled break and continue. Existing algorithms which solve this problem for WebAssembly include:

Cheerp's Stackifier ─ described in this Medium post.
Emscripten's Relooper ─ described in this paper.
LLVM's WebAssemblyCFGStackify algorithm ─ I can't find a decent explainer, but this seems to be based on it, and this claims to be a simplified version.

These approaches should also work for compiling to Javascript, since Javascript has all of the control-flow statements that WebAssembly uses.
---
### Answer by username_1 on 2023-05-25. Score: 9
Check out the Relooper algorithm, originally created for the Emscripten C-to-Javascript compiler. It describes a way to compile arbitrary control flow graphs using only if, while, and labelled break statements (those break statements that can break out of an outer loop). Relooper is also used in compilers that target WebAssembly (which also doesn't have goto).

---

**Emscripten: an LLVM-to-JavaScript compiler**  
Alon Zakai (2011) <https://dl.acm.org/doi/10.1145/2048147.2048224>

**Beyond Relooper: recursive translation of unstructured control flow to structured control flow**  
Norman Ramsey (2022) <https://dl.acm.org/doi/10.1145/3547621>
> **Comments:**
> **username_2** (2023-06-30): I found it hard to follow the Emscripten paper, so I'll have to check out the Beyond Relooper paper to see if it's easier to grasp its concepts!  
---
### Answer by username_4 on 2023-05-24. Score: 4
Finite State Machines
An FSM is an abstract machine where each step is represented as a state, and where computation is a sequence of state transitions.
Each labelled subroutine is its own state, which you can represent this way:
machine main()
{
    int f;
    int g;
    state start
    {
        f = getchar();
        if(f < 3) {
            goto loop;
        }
        else {
            goto start2;
        }
    }
    state loop
    {
        f += 1;
        if(f < 3) {
            goto loop;
        }
        else {
            goto start2;
        }
    }
    state start2
    {
        g = getchar();
        f += g;
        if(g > 5) {
            goto loop;
        }
        else {
            for(int j = 0; j < 12; ++j) {
                if(j == f) {
                    goto start;
                }
                else if(j == -f) {
                    goto end;
                }
            }
        }
    }
    state end {}
}

In a C-like language, that is while/switch. And you can simplify some loop states using do while. And since you mention JavaScript, here's your example code ported to JS:
function main()
{
    let _state = 0;
    let f, g;
    _fsm: while(true) {
        switch(_state) {
        case 0:
            f = getchar();
            if(f < 3) {
                _state = 1;
                continue _fsm;
            }
            else {
                _state = 2;
                continue _fsm;
            }
        case 1:
            do {
                f += 1;
            } while(f < 3);
            _state = 2;
            continue _fsm;
        case 2:
            g = prompt();
            f += g;
            if(g > 5) {
                _state = 1;
                continue _fsm;
            }
            else {
                for(let j = 0; j < 12; ++j) {
                    if(j == f) {
                        _state = 0;
                        continue _fsm;
                    }
                    else if(j == -f) {
                        _state = -1;
                        continue _fsm;
                    }
                }
            }
        case -1:
            break _fsm;
        }
    }
}
---
