Post by ***@gmail.comWell, compiler algorithms were hard to invent. But now
they are described in books and it is not hard to
reproduce algorithm from a book.
It is when you don't understand the algorithm in the book.
My brain wasn't designed for complex algorithms.
I have other skills though.
Hmm, algorithms in compiler are really not more complicated
that algorithms in OS, database, BBS or even text editor.
Actually main thing is bookkeeping: you need to make sure
that right information is at places that need it.
There is problem of scale if you go for full compiler.
But this is not too bad. Self compiling toy compiler
for subset of C should be doable in 2-3 kloc. At about
20-25 kloc you should be able to get C90 compilance.
In our time those are not really big programs.
Post by ***@gmail.comConcerning SubC, it looks like rather bad start for
a full C compiler.
"full" meaning what level of the standard? I'm only
interested in C90.
Already C90 have many things which are problematic to add
to SubC. For me non-negotiable is full support for structs.
That does not need much code, but AFAICS it includes change
of frequently used compiler data structures, that is lot
of code to change.
Floating point is another thing: it is reasonable to skip
floating point in initial toy and add it only at later
stage. But compiler structure should support easy addition,
which means support different modes of variables. Which
essentially meanst that if you want to add floating point
later you should support different size of short and long
releatively early.
Another thing is bitfields: personally I make little use
of them, but sometimes they are quite useful. And there
are a lot of programs using them.
Let me add that if I were to pick my subset of C it
probably would inculde limited VLA-s. Namely, AFAIK code
like:
void mat_add(int n, int a[n][n], int b[n][n]) {
int i,j;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
a[i][j] += b[i][j];
}
}
}
is valid C99. And one could write essentially identical
code in Fortran66 and it is not very hard to support
(full VLA support need much more effort).
Post by ***@gmail.comThere are design decisions that
make it more complex than necessary simultanously
limiting what it can do. In particular using two symbol
tables and acumulator model for code generation.
Could you explain these problems in more detail please?
I'd like to understand what is wrong with it.
Scope in programming languages is recursive. You may claim
that in C there are "really" only two scopes: file scope and
function scope, but C90 standard says differently. So,
for correct implementation of C you need to handle multiple
scopes. Now, there are well established methods to handle
multiple scopes using single symbol table. Simplest one
just puts new definitions at and of symbol table. It also
remembers position in symbol table corresponding to start of
scope and when inner scope ends simply resets end to remembered
position (which effectively removes all entries from inner
scope and restores entries from outer scope). There is
variation of this using hash tables. So two symbol
tables in SubC means that you get _more_ complicated
compiler which is less capable than simpler one.
Actually, the two symbol tables are tip of iceberg.
Natural handling of types is recursive: pointer type
contains type of thing pointed to, structure has list
of fields and each of fields has its own type. In
compiler it is convenient to have function types,
such type has type of return value and argument types
(C does not have function types but have pointers to
functions and function type in compiler simplifies
handling of pointers). SubC apparently encodes
several combinations of types as integers and
uses switches to handle them. Each switch branch
needs its own code and due to combinations you
get more code. With recursive handling you have
less cases, so simpler code and more capable
compiler.
After second thought I think there is reason for
unnecessary complexity in SubC. Namely, IIUC
oryginally SubC had no support of structures.
Nils wanted self-compilation which implied
no structures in compiler. Recursive approach
heavily depends on structures so Nils probably
thought that without structures "flat" approach
is simpler. But avoidance of structures (I saw
only one structure type in SubC source) means
that code is more complicated and harder to
understand.
Concerning accumulator machine: there are several
machine models usable for code generation. Basically,
main part of compiler generates instructions for
simple abstract machine and code generator is
responsible for translating instructions from
abstract version to actual machine code. In
simplest version each abstract instruction is
separately translated to one or more machine
instructions.
Popular abstract machines are stack machines
and 3 address representation. What is wrong
with accumulator machine as abstract target?
Well, there is one accumulator so there are
a lot of moves to/form accumulator. Which
means more work when generating instructions
for abstract machine and more work in code
generator. And you either get poor object
code or spent significant effort combining
abstract instructions into machine instructions.
Compared to that 3 address representation
means that when generating abstract instructions
you need to allocate space for temporaries
(which is easy) and except of temporaries
other parts are easier. When generating
machine instructions from 3 address
representation code generator is simpler
and has more opportunity to better use machine
instructions.
Let me add that I did really simple code
generator using 3 address representation
(as part of a toy compiler). This was mainly
to see how bad the generated code will be.
Initially it was really bad, maybe a little
worse than code from SubC. But I noticed
a few little tricks. The main being that
each expression has some destination and
machine code generator directly produces
result in this destination. In abstract
level a little care ensured that final
destination is propagated down, so many
moves generated by earlier version are no
longer needed.
Maybe as another comparison, I also did machine
code generator for "production" compiler (this was
addition to existing compiler, other part were already
done, but did not support machines that I wanted). This
was fancy language having more features than
C. Code generator for x86_64 has 2291 lines.
Code generator for 32-bit arm has 1579.
Here representation is again 3 address representation
(but there is explict stack and address may be
on the stack). I dare to say that both generate
_much_ better code than SubC. The code is
not as good as I would wish, mainly because
register allocation is done outside and is
quite naive (first few variables go to
available registers, other are no the stack).
As I mentioned, language is rather fancy.
Many things were handled in machine independent code.
But my code generator had to do loads/stores of
various sizes (including arbitrarily sized bitfields)
and had special support for some higher-level
constructs. My point here is that you can
get to much better machine code than SubC in
releatively simple compiler (in particular code
was essentially generated separately for each
abstract instruction). But design choices
matter: due to earler design choice I was
stuck with suboptimal register allocation.
OTOH representation of addresses had place
for offset and autoincrement/autodecrement.
Which means that on x86_64 equivalent of
a = t[i + 5];
could translate to single machine instruction
(assuming that a was allocated in register
and t and i were available in registers and
size was OK for x86 SIB mode). Similarly
on arm equivalent of
*(q++) = *(p++);
translated to two machine instructions (thanks
to availabliity of autoincrement on arm).
Anyway, you want public domain code, but licence does
not prevent you learning from licenced code.
You can adapt the same design choices in your
program. Or when something does not work well
you can avoid this.
--
Waldek Hebisch