24
$\begingroup$

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:
}
$\endgroup$

3 Answers 3

17
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ Jun 30, 2023 at 2:47
4
$\begingroup$

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;
        }
    }
}
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .