Re: transpiling to low level C

bart <bc@freeuk.com> wrote:

On 17/12/2024 18:46, Waldek Hebisch wrote:

bart <bc@freeuk.com> wrote:

>
If you try to extract any meaning, it is that any control flow can be
expressed either with 'goto' or with 'recursive functions'.
>
This is what I picked up on. Who on earth would eschew 'goto' and use
such a disproportionately more complex and inefficient method like
recursive functions?

 
Due to silly conding standard?  Or in language that does not have
'goto'.

 
It was suggested that 'theoretically', 'goto' could be replaced by
recursive function calls.
 
Whether still within the context of a language with no other control
flow instructions, is not known. The suggester also chose not to share
examples of how it would work.

The example I gave (and you snipped) was supposed to explain how
the technique works, but it seems that it is not enough.  So
let us look at another example.  Start from ordinary C code that
only uses global variables (this is not strictly necessary, but
let as make such assumption for simplicity):

int n;
int * a;
int b;
int i;

...
    /* Simple search loop */
    for(i = 0; i < n; i++) {
        if (a[i] == b) {
            break;
        }
    }

First, express flow control using only conditional and unconditional
jump:

  l0:
    i = 0;
    goto l3;
  l1:
    int c1 = a[i] == b;
    if (c1) {
      goto l4;
    } else {
      goto l2;
    }
  l2:
    i++;
  l3:
    int c2 = i < n;
    if (c2) {
        goto l1;
    } else {
        goto l4;
    }
  l4:
    ;

Note, I introduced more jumps than strictly necessary, so that
hunks between labels end either in conditional or unconditional
jump.

Next, replace each hunk staring in a label, up to (but not
including) next label, by a new function.  Replace final jumps
by function calls, for conditional jumps using the same trick
as in previous 'silly' example:

int n;
int * a;
int b;
int i;

void l2(void);
void l3(void);
void l4(void);

void l0(void) {
    i = 0;
    l3();
}

void l1(void) {
    void (*(t[2]))(void) = {l4, l2};
    int c1 = a[i] == b;
    (*(t[c1]))();
}

void l2(void) {
    i++;
    l3();
}

void l3(void) {
    void (*(t[]))(void) = {l1, l4};
    int c2 = i < n;
    (*(t[c2]))();
}

void l4(void) {
}

Note: 'l4' is different than other functions, intead of calling
something it returns, ensuring that the sequence of calls
eventually terminate.

I hope that principles are clear now.  If you compile this
with gcc at -O2 you will see that there are no calls
in generated code, only jumps.  Slightly better code is
generated by clang.  Note that generated code uses stack
only for final return.

BTW: you can see that currently tcc do not support this
coding style, that is code generated by tcc dully performs
all calls leading possibly to stack overflow and to
lower performance.  Code generated by tcc from "jumpy"
version looks slightly worse than code generated by
clang from version using calls.

--
                              Waldek Hebisch