Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1238 > unrolled thread

Best "simple" C Compiler I've ever seen

Back to article view | Back to comp.compilers

Contents

  Best "simple" C Compiler I've ever seen andrewchamberss@gmail.com - 2014-05-04 18:23 -0700
    Re: Best "simple" C Compiler I've ever seen federation2005@netzero.com - 2014-06-30 12:42 -0700
    How to type braces for computed gotos (was: Best "simple" C Compiler I've ever seen) federation2005@netzero.com - 2014-07-18 14:44 -0700
      Re: How to type braces for computed gotos glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-19 02:21 +0000
        Re: How to type braces for computed gotos Ivan Godard <ivan@ootbcomp.com> - 2014-07-18 21:59 -0700
        Re: How to type braces for computed gotos federation2005@netzero.com - 2014-07-21 10:32 -0700
      Re: How to type braces for computed gotos (was: Best "simple" C Compiler I've ever seen) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-07-21 11:45 +0000
        Re: How to type braces for computed gotos glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-21 16:19 +0000
        Re: How to type braces for computed gotos wclodius@earthlink.net (William Clodius) - 2014-07-21 21:44 -0600
          Re: How to type braces for computed gotos glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-23 00:35 +0000
            Re: How to type braces for computed gotos wclodius@earthlink.net (William Clodius) - 2014-07-22 22:36 -0600
              Re: How to type braces for computed gotos anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-07-25 22:38 -0400

#1238 — Best "simple" C Compiler I've ever seen

https://github.com/rui314/8cc

Self hosting, extremely well written, and seems geared towards simple
but complete code rather than being a complicated monolith. In my
opinion this compiler hasn't gotten enough attention so I'm posting it
here for people who haven't seen it.

Cheers,
Andrew Chambers

[toc] | [next] | [standalone]

#1289

On Sunday, May 4, 2014 8:23:05 PM UTC-5, andrewc...@gmail.com wrote:
> https://github.com/rui314/8cc
> Self hosting, extremely well written, and seems geared towards simple
> but complete code rather than being a complicated monolith. In my
> opinion this compiler hasn't gotten enough attention so I'm posting it
> here for people who haven't seen it.

Simple indeed it is. However, one of the issues I've always had with HLL's --
until recently -- was the neglect of the (by far) most important part of a
compiler: how it defines the enclosing envuronment; i.e. the "run-time"
system.

In particular, by "neglect" what I mean is neglect of the pressing need in
many applications to build in concurrency at the language level. In other
words, a run-time system that is multi-threaded at the core.

With the advent of the latest ISO standard, a lot of this has begun to be
addressed.

This is something I've been going through for a while now. The last open draft
available, in the case of C, I think is n1570, as indicated in the 8cc link
you provided. For C++ I think n3242 is the last open draft. With the way the
were written, I ended up reformatting and cleaning up my copy (of the earlier
version n1516 however) -- 22 pages for the first 5 parts alone (out of 7) and
225 pages or so for parts 1-12 of the C++ standard. I wish I could post the
cleaner version, it's easier to read and understand.

But anyway: the change is not merely a minor tweak in an evolving language,
but an entire paradigm shift. In particular, Section 5.1.2.4 of the standard
is ground zero of this paradigm shift, not merely a minor addition to the
standard. The same wording was also used in the revised C++ standard, in
section 1.10.

So, there is the challenge for anyone wishing to keep that same simplicity and
perhaps to even experiment with the compiler you cited (because it's already
so simple to begin with and thus easy to work on). Build a new run-time system
that is sufficiently powerful to handle the needs of contemporary CPUs and to
embody the latest ISO standard.

A long time ago, in the context of embedded systems, I devised a very simple
run-time framework I called "The World's Smallest Multitasking Kernel" (WSMK).
The source of the name is that it comprises just 4 system calls: a "Pause"
routine" to get a thread to wait on an event, a "Resume" to resume whoever is
waiting on the event, a "Spawn" to create a new thread and "Exit" to commit
suicide.

The simplicity in its conception lay in two key places:
(1) Exit was put on the bottom of the stack of a newly spawned thread

(2) No task control blocks: everything is put on the stack when pausing (Not
an essential feature of WSMK though)

(3) Integration with interrupts and exceptions: all of them are encapsulated
within the run-time system so that each produces a "resume" on its own event.

Thus, an application would never need to write any interrupt handlers or
callbacks, but could write straight-line threads.

(4) The ability to nonetheless go underneath the run-time system with direct
implementations of interrupt handlers.

The pressing question was always this: could something this simple actually
work for handling more complex multi-threaded applications. As it turns out,
what's described here is essentially equivalent to what's known as the "Pi
Calculus" -- something I only recently learned of a few months ago. The Pi
Calculus is complete. (That means anything any concurrency formalism is able
to express can be expressed within the framework of the Pi Calculus).

But what's missing is the question of how to define scoping, linkage,
persistence, etc. for variables; and more importantly, a *standard* that
mandates how these things are to be treated. That's what the latest ISO
standards have started to address.

Also missing is a question of what language constructs are to be atomic, where
and how basic processes (e.g. printf) could be interspersed with other
threads' actions, etc. That too has been partially resolved with the somewhat
detailed concurrency formalism spelled out in the above-mentioned section.

So, this gets us back to the central question: which is that the most
important part of the compiler is and has always been ... how everything is to
be hung together and orchestrated, the run-time system.

I think that much of this can be simplified yet further by replacing the
traditional call-return semantics by continuation semantics. And so, what I'm
seriously considering doing is devising such a base-level formalism that has
the multi-threaded run-time system, along with compilation that is entirely
based on continuation semantics (i.e. no run-time stacks or frames per se.)

Interestingly, in the process of reviewing different software for numeric
processing (much originally in Fortran) I notice that one library -- AlgLib --
appears to have put in its own multi-threaded runtime system ... but one that
only looks like the next to last stage in the evolution that WSMK underwent in
1990-1991 before it reached its final form. The difference is that AlgLib's
runtime system runs on Windows and Linux, whereas WSMK never (yet) went beyond
DOS.

[toc] | [prev] | [next] | [standalone]

#1323 — How to type braces for computed gotos (was: Best "simple" C Compiler I've ever seen)

On Sunday, May 4, 2014 8:23:05 PM UTC-5, andrewc...@gmail.com wrote:
> https://github.com/rui314/8cc
> Self hosting, extremely well written, and seems geared towards simple
> but complete code rather than being a complicated monolith.

On that count: usually when I redo a source (reformat, reanalyze the math,
make more effective use of the language, etc.) it comes out to 50% reduction
by lines 30% by bytes; which is consistent across thousands of source files.

The only exceptions I've encountered to date are stuff I earlier reduced (30%
by lines if it made use of an earlier dialect of the language), stuff from
AT&T (which does not reduce much, e.g. CFront) and the source for this
compiler.

So by that count, it's well-written and compact.

There is one feature the compiler tests for that I assume the language also
has in it that I haven't seen much of before: the computed goto. What's I
don't quite understand how the branches are being typed. A computed goto
inside a void routine has the branches typed (void *), with the individual
items accessed in effect as references to (void *).

The branches are essentially continuations. So the question here is how are
continuations being typed. From the example used in the distribution, either
(A) all continuations are typed (void *) or they are being typed (T *) when
they occur inside a function that returns type T.
[That's an extension. In standard C, you can only goto a label. -John
Perhaps it's similar to this GCC extension
https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html#Labels-as-Values]

[toc] | [prev] | [next] | [standalone]

#1325 — Re: How to type braces for computed gotos

federation2005@netzero.com wrote:

(snip)

> There is one feature the compiler tests for that I assume the language also
> has in it that I haven't seen much of before: the computed goto. What's I
> don't quite understand how the branches are being typed. A computed goto
> inside a void routine has the branches typed (void *), with the individual
> items accessed in effect as references to (void *).

(snip)

> [That's an extension. In standard C, you can only goto a label. -John
> Perhaps it's similar to this GCC extension
> https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html#Labels-as-Values]

In standard C you can only goto label constants.

In PL/I you can goto label constants or variables.

In standard C, you should be able to make an array of jmp_buf and
then longjmp() to an element of the array. However, you can only
longjmp() to an element once.

I don't know that I ever tried, but I believe you can GOTO a PL/I
label variable more than once, as long as it still makes logical
sense to do it. (That is, it isn't inside a procedure that has
already returned.)

-- glen
[Ugh. -John]

[toc] | [prev] | [next] | [standalone]

#1326 — Re: How to type braces for computed gotos

On 7/18/2014 7:21 PM, glen herrmannsfeldt wrote:
> federation2005@netzero.com wrote:
>
> (snip)
>
>> There is one feature the compiler tests for that I assume the language also
>> has in it that I haven't seen much of before: the computed goto.

Mary2 had typed labels, that mimicked the common assembler practice of
loading a value to a register and jumping to the code that used it. Thus
"label int32 eat1;" declared a label variable in which the carried data
was an int32.

This made use of the Mary2 lack of operator precedence and strict
left-to-right evaluation. The "current operand" was the result of
evaluating everything to your left, and it formed the left operand of
the operation immediately to your right. The carried value of the goto
replaced the current operand of the expression containing the label. Thus:
    if pred() then a[i] + 1 go eat1;
    ...;
    x-y*z eat1: *2 =: w;
If pred() is true then the execution is:
    a[i]+1*2=:w;
while if false it is:
    x-y*z*2=:w;
Note the absence of precedence; that last turns into asm:
    load   x
    load   y
    sub
    load   z
    mul
    con    2
    mul
    store  w
or register machine equivalent.

The notion of "current operand" and the ability for control flow to
carry data was surprisingly useful, primarily because it permitted loops
to be value-yielding, as is appropriate in an expression language like
Mary. As a result, search loops did not need extraneous variables to
hold the value found for use after the loop. The actual goto form was
uncommon, but where appropriate it greatly simplified the code and
improved readability, and the result engendered a style that was vaguely
reminiscent of continuation-passing style.

One-pass compilation was near-trivial.
[Fortran had assigned goto, and Cobol had ALTER, but that still doesn't
mean it was a good idea. -John]

[toc] | [prev] | [next] | [standalone]

#1342 — Re: How to type braces for computed gotos

On Friday, July 18, 2014 9:21:28 PM UTC-5, glen herrmannsfeldt wrote:
> > [That's an extension. In standard C, you can only goto a label. -John
> > Perhaps it's similar to this GCC extension
> >
https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html#Labels-as-Values]
> In standard C you can only goto label constants.

I read the type from context. The compiler test uses a prefix "&&" operator,
which is the same as the one used in GCC for addressing goto labels.

The particular points of interest and contact are several:

One, it indirectly hooks up with an earlier thread here on multi-level
jumps.  This leads directly to the notion of continuations, with the
archetypical case in point being Scheme ...

Two, ... and a second case in point being the old stand-by DC, which
has never received a solid well-founded standardization because of its
heavy use of continuations (i.e. a good high-level language analogue
of DC's string-based "execute" command).

Three, both these and the computed goto lead directly to the notion of
multi-entry point routines, coroutines and multi-threaded computation.
(Which ties to the thread about "the most important part of a
compiler").

I was hoping for a more robust typing scheme to be in place for
continuations since the question of how to type continuations has
always been a major road block for me, and it looked like this
compiler might have been experimenting with some kind of
continuation-typing, more robust than the one-size-fits-all "solution"
that GCC has.

In GCC itself, it might be worth considering an upgrade to
continuations that inherit their type from the return type of the
function body they reside in (or: if lambdas are allows, like Java or
C++ ... from the return type of the enclosing lambda).

[toc] | [prev] | [next] | [standalone]

#1338 — Re: How to type braces for computed gotos (was: Best "simple" C Compiler I've ever seen)

federation2005@netzero.com writes:
>There is one feature the compiler tests for that I assume the language also
>has in it that I haven't seen much of before: the computed goto. What's I
>don't quite understand how the branches are being typed. A computed goto
>inside a void routine has the branches typed (void *), with the individual
>items accessed in effect as references to (void *).
>
>The branches are essentially continuations. So the question here is how are
>continuations being typed. From the example used in the distribution, either
>(A) all continuations are typed (void *) or they are being typed (T *) when
>they occur inside a function that returns type T.

I guess this compiler implements the labels-as-values extension of GNU
C (aka "computed goto", but see the Fortran note below).  The type of
a label is always void *; static typing fans might prefer a separate
label type (or a whole type system for labels), but I guess that the
intersection between static typing fans and the users of this
extension is very small.  I have used labels-as-values extensively and
I have not produced errors stemming from confusion between labels and
other occurences of void *.

BTW, in Fortran this feature is called "assigned goto", and it uses
integer variables (i.e., not a special type, either) for storing the
labels (and therefore needs a separate syntax "assign 50 to l" instead
of just writing "l=50").  Fortran also has a feature called "computed
goto", but that is closer to a C switch than a GNU C "goto *".

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [next] | [standalone]

#1340 — Re: How to type braces for computed gotos

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:

(snip)

> I guess this compiler implements the labels-as-values extension of GNU
> C (aka "computed goto", but see the Fortran note below).

(snip)

> BTW, in Fortran this feature is called "assigned goto", and it uses
> integer variables (i.e., not a special type, either) for storing the
> labels (and therefore needs a separate syntax "assign 50 to l" instead
> of just writing "l=50").

The ASSIGN statement and assigned GOTO trace back to the original
Fortran compiler, now often called Fortran I.

The SUBROUTINE, CALL, and FUNCTION statements came in with Fortran II.
The only subroutine call mechanism available with the Fortran I system
was to ASSIGN a statement label to return to to some variable, GOTO to
the subroutine, and then at the end of the subroutine GOTO back. While
the computed-GOTO was also available, I suspect that the efficiency
gain (both speed and code size) on a 36 bit word vacuum tube computer
available, I believe, with between 8K and 32K words of magnetic core
memory.

But ASSIGN and the corresponding GOTO were removed from the standard
as of Fortran 95. The suggested replacement is the comptued GOTO.
Presumably someone should be able to write a program to automate the
conversion.

> Fortran also has a feature called "computed goto", but that is
> closer to a C switch than a GNU C "goto *".

The computed GOTO also traces back to Fortran I. It allows one to
select a statement label based on an index between 1 and the number of
labels available. The effect when the index variable is not in range
was undefined from Fortran I through the Fortran 66 standard. Fortran
77 defined an out of range index to continue on to the following
statement.

The computed GOTO is on the obsolescence list, though as of Fortran
2008 still hasn't been removed. As indicated, it can be replaced by a
SELECT CASE construct. But a SELECT CASE with a large number of GOTO
statement has to be uglier and less readable than a computed GOTO
statement.

-- glen

[toc] | [prev] | [next] | [standalone]

#1344 — Re: How to type braces for computed gotos

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:

> I guess this compiler implements the labels-as-values extension of GNU
> C (aka "computed goto", but see the Fortran note below).  The type of
> a label is always void *; static typing fans might prefer a separate
> label type (or a whole type system for labels), but I guess that the
> intersection between static typing fans and the users of this
> extension is very small.  I have used labels-as-values extensively and
> I have not produced errors stemming from confusion between labels and
> other occurences of void *.
>
> BTW, in Fortran this feature is called "assigned goto", and it uses
> integer variables (i.e., not a special type, either) for storing the
> labels (and therefore needs a separate syntax "assign 50 to l" instead
> of just writing "l=50").  Fortran also has a feature called "computed
> goto", but that is closer to a C switch than a GNU C "goto *".

Not quite the rough equivalent of a C switch statement is the Fortran 90
SELECT CASE. A Fortran computed GO TO, as with an assigned GO TO, does
not have a syntactic block associated with it, and can be set up to go
to any label within the current program or sub-program.

[toc] | [prev] | [next] | [standalone]

#1346 — Re: How to type braces for computed gotos

William Clodius <wclodius@earthlink.net> wrote:

(snip on labeled variable GOTO, Fortran ASSIGNed GOTO, and such)

> Not quite the rough equivalent of a C switch statement is the Fortran 90
> SELECT CASE. A Fortran computed GO TO, as with an assigned GO TO, does
> not have a syntactic block associated with it, and can be set up to go
> to any label within the current program or sub-program.

Well, there is no rule that you have to write ugly code in Fortran.
You can indent and comment, and otherwise arrange things in a more
orderly way.

In the case of computed GOTO, you could arrange the code for each
choice one after another, in the same order as the labels, and with
comments indicating which choice went to each one.

If you consider something like Duff's device, then it isn't so obvious
that computed GOTO is so different from C's switch/case.  (Well, when
the labels are sequential starting at one.)

As I noted previously, the Fortran standard now considers SELECT CASE
as a replacement for computed GOTO, though the latter hasn't yet been
removed from the standard.

-- glen

[toc] | [prev] | [next] | [standalone]

#1348 — Re: How to type braces for computed gotos

glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:

> William Clodius <wclodius@earthlink.net> wrote:
>
> (snip on labeled variable GOTO, Fortran ASSIGNed GOTO, and such)
>  ...
> If you consider something like Duff's device, then it isn't so obvious
> that computed GOTO is so different from C's switch/case.  (Well, when
> the labels are sequential starting at one.)
>
> As I noted previously, the Fortran standard now considers SELECT CASE
> as a replacement for computed GOTO, though the latter hasn't yet been
> removed from the standard.

In the case of Anton I think for the applications he is best know for,
high performance interpreters, the lack of syntactic block is a minor
advantage in that the

100 SELECT CASE(i)
       CASE(0)
       ...
       GO TO 100
       CASE(1)
       ...
       GO TO 100
       CASE(2)
       ...

can be replaced by

       GO TO(10, 11, 12, ...) I
10    ...
       GO TO(10, 11, 12, ...) I
11    ...
       GO TO(10, 11, 12, ...) I
12    ...

Saving an extra step in indirection. The bigger problem is the fall
through semantics for out of range with its implicit additonal test and
branch before the goto's implicit branch table. That can be avoided by a
modulo operation

GO TO(10, 11, 12, ...) MODULO(I, N) +1

where N is the number of labels appearing in the computed GOTO. If I is
an 8 bit integer and N is 256 a sufficiently smart compiler should
recognize the semantics of an unsigned 8 bit integer, fit the jump table
in a single level 1 cache line, optimize out the MODULO, the addition of
1, and the test for out of range and give him the efficiency he used to
get with gcc's "computed goto".  Whether that sufficintly smart compiler
is gfortran with gcc's backend would be a different matter.

[toc] | [prev] | [next] | [standalone]

#1349 — Re: How to type braces for computed gotos

wclodius@earthlink.net (William Clodius) writes:
>glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:
>
>> William Clodius <wclodius@earthlink.net> wrote:
>>
>> (snip on labeled variable GOTO, Fortran ASSIGNed GOTO, and such)
>>  ...
>> If you consider something like Duff's device, then it isn't so obvious
>> that computed GOTO is so different from C's switch/case.  (Well, when
>> the labels are sequential starting at one.)
>>
>> As I noted previously, the Fortran standard now considers SELECT CASE
>> as a replacement for computed GOTO, though the latter hasn't yet been
>> removed from the standard.

SELECT CASE may or may not be closer to switch than Fortran's computed
GOTO, but my claim was that Fortran's computed GOTO is closer to C
switch than to GNU C's labels-as-values (often called "computed goto",
too).  You make a good point from the view of usage, but I was
thinking more about implementation:

Fortran's computed goto does a range check, a table lookup and an
indirect branch.  And so does C's switch (well, the compiler can also
use other implementations, but that's certainly the classical
implementation, and it is probably used by every compiler for densely
populated cases).

In contrast, GNU C's labels-as-values and Fortran's assigned goto deal
directly with code addresses: The code address of a label is stored in
a variable (or more complex structure), and the corresponding goto
just performs an indirect branch.

>In the case of Anton I think for the applications he is best know for,
>high performance interpreters, the lack of syntactic block is a minor
>advantage in that the
>
>100 SELECT CASE(i)
>       CASE(0)
>       ...
>       GO TO 100
>       CASE(1)
>       ...
>       GO TO 100
>       CASE(2)
>       ...
>
>can be replaced by
>
>       GO TO(10, 11, 12, ...) I
>10    ...
>       GO TO(10, 11, 12, ...) I
>11    ...
>       GO TO(10, 11, 12, ...) I
>12    ...
>
>Saving an extra step in indirection. The bigger problem is the fall
>through semantics for out of range with its implicit additonal test and
>branch before the goto's implicit branch table.

Actually the shared indirect branch is the bigger problem.  The range
check is predictable and costs almost nothing, while the shared
indirect branch has almost 0% prediction accuracy (in contrast to
about 50% accuracy if you have a separate indirect branch at the end
of every routine that implements a virtual machine instruction).

> That can be avoided by a
>modulo operation
>
>GO TO(10, 11, 12, ...) MODULO(I, N) +1
>
>where N is the number of labels appearing in the computed GOTO. If I is
>an 8 bit integer and N is 256 a sufficiently smart compiler should
>recognize the semantics of an unsigned 8 bit integer, fit the jump table
>in a single level 1 cache line, optimize out the MODULO, the addition of
>1, and the test for out of range and give him the efficiency he used to
>get with gcc's "computed goto".

Even if you eliminate the range check and produce separate indirect
branches, the Fortran computed goto (or SELECT CASE) and C switch
still perform the table lookup, which is not needed with GNU C's
labels-as-values or Fortran's assigned GOTO.  The performance impact
is not as big as with separate indirect branches, but it's still there
and can be eliminated.  The technique is called direct-threaded code.
In Fortran it might look like this:

      ASSIGN 11 TO PROG(0)
      ASSIGN 11 TO PROG(1)
      ASSIGN 10 TO PROG(2)
      IP=0
      GOTO PROG(IP)

10    ... code for virtual machine addition ...
      IP=IP+1
      GOTO PROG(IP)
      GOTO I
11    ... code for virtual machine constant ...
      IP=IP+1
      GOTO PROG(IP)
      GOTO I

Of course in a real interpreter PROG would not be initialized by
hard-coded ASSIGNs, but the ASSIGNs would initialize an instruction
array, and the interpreter front end would fill PROG from there; this
essentially moves the indirection from execution to the interpreter
front-end (one indirection per VM instruction instead of one
indirection per VM instruction execution).

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web