well, recently I came up with an idea, but it has turned into a bit of a
mess on me...
I have an existing C compiler I wrote before, and it is organized about
like
this:
Preprocessor;
Parser;
Upper Compiler, converts syntax trees to RPNIL;
Lower Compiler, converts RPNIL to assembler;
Assembler;
Linker.
so, the upper-compiler ends up being fairly sparse, mostly being a fairly
dumb converter.
the output, I call RPNIL, is a vaguely Forth or PostScript like language
representing the intermediate version of the language.
some of the basic types-related processing, constant folding, some branch
elimination, ... has been done before any of this RPNIL code is generated
(likewise, the various high level constructions have been decomposed into
labels and conditional jumps).
meanwhile, the lower-compiler does much of the "heavy lifting",
implementing
many things I had not really originally intended (nearly the entire types
tower, operator overloading, inlining, ...), and goes all the way down to
machine code (when this compiler project was started, it was originally
assumed that this lower end would be simple and stupid, but it ended up
being one of the largest and complicated pieces of the project).
so, an idea was considered:
I can split this compiler into 2 major stages:
an upper-lower compiler, which would do most of the high-level processing
(the it would then compile from RPNIL to some other representation);
a lower-lower compiler, which would take this representation and convert
it
into machine code.
starting out, I had made the (incorrect) assumption that this would be an
easy process or reorganizing the code, but looking at it, it is unlikely
to
be anywhere near this simple (the code is both inconsistently structured
and
heavily interconnected).
if I were to follow things how I began to split them, the lower-lower
compiler (I had started calling it VRM), I would end up with an abstracted
x86-ASM like language.
basically, it would differ from x86 ASM largely by glossing over many of
the
differences between x86 and x86-64, implementing more types, and
essentially
merging/orthogonalizing the SSE registers and GPRs, for example, in
allowing
64 and 128 bit integers as built-in types, ... but, it would be a lot
lower-level than RPNIL in that it would not automatically handle the
calling
conventions, abstract types (such as typed pointers, structures, arrays,
....).
as this had been imagined, it would follow the x86-style "operator dest,
source" instruction format. the exact register handling would be handled
by
a register allocator, and register names would consist of an id and some
letters giving the type.
for example (this stage of the idea):
push x0f4 ;push float vector to stack
div x5o, x3o ;divide 128 bit integers
mul x1f4, x7f4 ;SIMD multiply ('mulps')
sub x2g, x4g ;SSE subtract ('subsd')
pop x3g ;pop double into x3
push r1q ;push qword in r0
mov r2q, x6q ;mov qword in x6 to r2
....
a subsequent idea was then that I could further generalize things, and
switch over to a TAC+SSA based representation:
mov.i r16 3
mov.i r17 4
mov.i r18 2
mul r20 r16 r17
add r23 r18 r20
phi r24 r23 r26
L0:
mov.i r25 1
sub r26 r24 r25
cmp_lez r27 r26
jmp_t r27 L0
....
which would allow some more "interesting" features, and can be fairly
easily
converted into the two-register form internally by using dependency
analysis
(we can take note that, if a value is never used again, we will not see it
again, thus a "true" three-address form is rare, and will involve
duplicating the register).
in the existing RPN-compiler, much of this dependency tracking is an
implicit part of the stack machinery, since when we pop two items from the
stack, we can safely assume we will not see them again (thus, dup or
similar
is needed if we want to keep the value around). internally, a two-oprand
register-based approach took hold, primarily because this was much easier
to
work with (the stack serving, in large part, to push and pop abstract
literals and registers).
but, it seems a little silly to have an RPN-based language that compiles
into SSA based language.
may as well directly compile from syntax trees into SSA, as this would
seem
to make more sense. however, doing this would end up with me rewriting
damn
near the entire compiler (as opposed to just a decent chunk of it...).
technically, it would be a lot easier to stick with a two-operand form
(similar to x86), and sticking with RPNIL as the main IL (even simpler, is
to implement this lower portion more as a mass of library code that is
directly driven by the RPNIL compiler, which is a lot closer to the
original
plan, and what I had originally started doing before all this came up).
however, TAC and SSA may make sense if they may later allow a lot more
features and optimizations (for example, constructions being, for whatever
reason, either not possible or extremely awkward with RPN).
or, I can do the basic library (serving as a codegen), and possibly later
write an SSA style frontend (and rework the upper compiler to target it
directly).
anyone have any thoughts?...
|
