Re: transpiling to low level C

bart <bc@freeuk.com> wrote:

On 18/12/2024 00:23, Waldek Hebisch wrote:

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.

 
It showed how to do conditional code without explicit branching. It
didn't seem to me to cover arbitrary gotos, or where recursion comes
into it.
 
(Actually I implemented it in my two languages to compare performance to
'straight' versions, however my test called silly() lots of times so it
wasn't a good test.)
 

 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};

                                ^^^^^^^
Should be
                                l2, l4

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

                               ^^^^^^
                               l4, l2

     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.

 
OK thanks for this. I tried to duplicate it based on this starting point:
 
 #include <stdio.h>
 
 int n=6;
 int a[]={10,20,30,40,50,60};
 int b=30;
 int i;
 
 int main(void) {
    for(i = 0; i < n; i++) {
         printf("%d\n",a[i]);
         if (a[i] == b) {
             break;
         }
     }
 }
 
This prints 10 20 30 as it is. But the version with the function calls
showed only '10'. If I swapped '{l1, l4}' in l3(), then I got '10 10 20'.

Sorry, there was a thinko: 1 is true and this is the second element
of the array, while I was thinking that the first one is true branch
and second is false branch.
 

I didn't spend too long to debug it further. I will take your word that
this works. (I tried 3 compilers all with the same results, including TCC.)
 
I don't fully understand it; what I got was that you first produce
linear code with labels. Each span between labels is turned into a
function. To 'step into' label L, or jump to L, I have to do L().

Yes.

There would still be lots of questions (even ignoring the problems of
accessing locals), like what the return path is, or how an early return
would work (also returning a value). Or what kind of pressure the stack
would be under.

OK, you take a function F, it has some arguments and local variables.
And some retrun type.  You create "entry function" to take the
same arguments as F and has the same return type as F.  You tranform
body as above, but now each new function has the same return type
as F and arguments are arguments of original function + extra arguments,
one for each local variable of F.  In "entry function" you call
function corresponding to first label passing it arguments and
initial values of local variables of F.  In each subseqent call
you pass argument and values around so that they are available
in each new function.  And the call is an argument to return
statement.  When you want to return you simply return value,
without performing a call.

Stack use depend on optimizations in your compiler.  With small
effort compiler can recognize that it will return value (possibly
void) from a call and replace such call by stack+register
shuffling + jump.  Actually when there is return value, you
have something like

   return lx(a0, a1, ..., ak);

which is easy to recognize due to 'return' keyword.  One also
need to check that types agree (C automatically applies integer
convertions, but such convertions may produce real code, so in
such case one needs normal call).  In void case one need to
check that there the call is textually last thing or that
it is followed by return statement.  Stack+register
shuffling may require some code before control transfer, but
call can be replaced by jump.

So, if compiler has tail call optimization, then there is no
more stack use than maximum needed by any of the functions.

Note: I described general transformation, partially to show
that 'if' is _not_ needed.  But similar style is used to
write code by hand.  In hand written code people do not
bother with transforming 'if', which makes tail call
optimization a bit more complicated.  OTOH, unlike rather
ugly code produced by mechanical transformation, hand
written code depending on tail call optimization may be quite
nice and readible.  There is potential trouble: sometimes
author thinks that a call is a tail call, but compiler
disagrees, leading to lower efficiency.

Of course, when compiler do not have tail call optimization,
then stack use may be quite high.

It looks like a crude form of threaded code (which, when I use that,
never returns, and it doesn't use a stack either).

IMO it is quite different than what I know as threaded code.
 

I've seen enough to know that it would be last kind of IL I would choose
(unless it was the last IL left in the world - then maybe).
 
There is also the oddity that eliminating a simple kind of branching
relies on more elaborate branching: call and return mechanisms.

One motivation for eliminating 'goto' is that it is not easy to
say what effect 'goto' has on variables.  I mean, variables keep
ther values, but when you may arrive to given point from several
places than values of variables depend on place that control came
from, and this may be hard to analyze.  In a sense functions have
the same problem, but there is well-developed technique to reason
about function calls.  So both jumps and function calls are
hard to analyze, but eliminating jumps allows re-use of work
done for functions.

More interesting and more practical would be replacing call/return by
'goto'! (It would need to support label pointers or indirect jumps,
unless runtime code modification was allowed.)

The point is that calls are strictly more powerful than jumps
(you get parameter passing and local variables).

--
                              Waldek Hebisch