Writing compilers, and example.c vs compile-i386.c

Writing compilers, and example.c vs compile-i386.c

[David Given]

[-- Attachment #1: Type: text/plain, Size: 2134 bytes --]

I'm wanting to write a compiler-like tool that's capable of generating
machine-code-like-stuff (don't ask, long story), and as such, have been
looking around for C compiler front ends that will make my life easier.
sparse looks extremely promising.

As such, I've been examining the two sample compilers, example.c and
compile-i386.c. These appear to generate i386-ish machine code, but do
so in entirely different ways. If I've understood them correctly,
example.c enumerates the instructions inside each function's basic
blocks, and uses sparse's pseudo_t support for doing register
allocation; while compile-i386.c enumerates the statements inside each
function, and does it's own register allocation.

Some basic testing with show_statement() and show_insn() reveals that
both approaches seem to yield similar but *different* pseudocode... with
different SSA phi functions. What's the difference between the two, and
do you have any suggestions as to which approach I should look at?

In addition, I'm afraid I'm going to have to use the D word... has
anyone written down anything about how all this stuff works? I'm afraid
it's rather a large mass of code to try and absorb in one go, and any
overview information would help me considerably. For example: if I put
together a noddy program that enumerates basic blocks (the example.c
approach) I see phi functions. Calling unssa() doesn't seem to help.
However, inserting instrumentation into example.c indicates that it
*doesn't* see phi functions (as far as I can tell). There's something
I'm simply not getting here --- does the removal of phis actually happen
inside the register allocator (which seems like the intuitive place for
it), and if so, what does unssa() actually do?

This is all with sparse 0.4.1. Is that current?

-- 
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
│ "I have always wished for my computer to be as easy to use as my
│ telephone; my wish has come true because I can no longer figure out
│ how to use my telephone." --- Bjarne Stroustrup


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: Writing compilers, and example.c vs compile-i386.c

[Mike Frysinger]

On Mon, Jun 16, 2008 at 7:04 PM, David Given wrote:
> I'm wanting to write a compiler-like tool that's capable of generating
> machine-code-like-stuff (don't ask, long story), and as such, have been
> looking around for C compiler front ends that will make my life easier.
> sparse looks extremely promising.

this may be worth investigating as well:
http://pcc.ludd.ltu.se/
-mike

Re: Writing compilers, and example.c vs compile-i386.c

[Christopher Li]

On Mon, Jun 16, 2008 at 4:04 PM, David Given <dg@cowlark.com> wrote:
> Some basic testing with show_statement() and show_insn() reveals that
> both approaches seem to yield similar but *different* pseudocode... with
> different SSA phi functions. What's the difference between the two, and
> do you have any suggestions as to which approach I should look at?

I would strongly recommend using the example.c rather than compile-i386.c.
If you want to do any thing interesting with the back end at all, using
the linearize byte code is the way to go.

> In addition, I'm afraid I'm going to have to use the D word... has
> anyone written down anything about how all this stuff works? I'm afraid
> it's rather a large mass of code to try and absorb in one go, and any
> overview information would help me considerably. For example: if I put
> together a noddy program that enumerates basic blocks (the example.c
> approach) I see phi functions. Calling unssa() doesn't seem to help.
> However, inserting instrumentation into example.c indicates that it
> *doesn't* see phi functions (as far as I can tell). There's something
> I'm simply not getting here --- does the removal of phis actually happen
> inside the register allocator (which seems like the intuitive place for
> it), and if so, what does unssa() actually do?

I haven't use the unssa() myself. It seems unssa() just replace the
phisrc instruction to a copy instruction. Let the source copy to a
temp register. Then on phi instruction it just copy that temp register
back to the phi node register.

The phi node is replaces with copy instruction inside unssa().
In the real machine code, the copy instruction can emit as "mov"
instruction.

As for linearize instructions. They are the internal representation
of the compiled program. In this representation, there is unlimited
pseudo register. Each pseudo is define in only one instruction. except
"OP_COPY" in the unssa().

Each function entry point has a list of basic blocks and each basic block
has a list of instructions. Most instruction is pretty straight for what
it does.

BTW, if you don't mind coding in C++, you can take a look at LLVM.

Chris

Re: Writing compilers, and example.c vs compile-i386.c

[David Given]

[-- Attachment #1: Type: text/plain, Size: 1943 bytes --]

Mike Frysinger wrote:
> this may be worth investigating as well:
> http://pcc.ludd.ltu.se/

That was actually where I started; it works pretty well, though after a
couple of hours of examining the code I realised that there was a good
reason why it looked like code that had been written 25 years ago and
then randomly hacked ever since. It's a little opaque, which is why I
ended up here.

Christopher Li wrote:
[...]
> I would strongly recommend using the example.c rather than compile-i386.c.
> If you want to do any thing interesting with the back end at all, using
> the linearize byte code is the way to go.

Yes, that's what I suspected --- being the more complicated file! Oh,
well, I've been examining it, and it's slow beginning to make sense.

However: I notice that the code seems to make use of OP_DEATHNOTE
instructions to mark hardregs as being dead. However, these are only
generated if track_pseudo_death(ep) is called --- and example.c never
calls this. It *is*, however, called if -vdead is specified on the
command line. Is this a bug in example.c or am I just misunderstanding
things?

(Also, the OP_DEATHNOTE instructions appear to occur *before* the
instruction that uses them last --- is this so that the instruction can
reuse the register is the code generator sees fit to do so?)

(In addition, I notice that once liveness tracking has been done phisrc
nodes get annotated with the desired shared register that the phi should
occupy; suddenly, the phi stuff all makes sense.)



(PS. Please don't cc me if you're also mailing the list --- I only need
one copy!)

-- 
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
│ "I have always wished for my computer to be as easy to use as my
│ telephone; my wish has come true because I can no longer figure out
│ how to use my telephone." --- Bjarne Stroustrup


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: Writing compilers, and example.c vs compile-i386.c

[Christopher Li]

On Tue, Jun 17, 2008 at 4:35 PM, David Given <dg@cowlark.com> wrote:

> Christopher Li wrote:
> However: I notice that the code seems to make use of OP_DEATHNOTE
> instructions to mark hardregs as being dead. However, these are only
> generated if track_pseudo_death(ep) is called --- and example.c never
> calls this. It *is*, however, called if -vdead is specified on the
> command line. Is this a bug in example.c or am I just misunderstanding
> things?

You understands it correctly. The example.c should call track_pseudo_death(ep).
It is a bug that I disable the dead node by default and forget to enable it for
example.c. For normal checking, death node is not needed, and if it is needed,
you can always generates it.

We should add the death node back for example.c. Patches are welcome
as well.

BTW, you shouldn't take example.c too seriously per Linus' suggestion.

> (Also, the OP_DEATHNOTE instructions appear to occur *before* the
> instruction that uses them last --- is this so that the instruction can
> reuse the register is the code generator sees fit to do so?)

I think so, it just let the code generator know that they don't need to preserve
that register any more for the next instruction they emit. It is a very naive
register allocations any way. Feel free to roll your own if you see fits.

> (In addition, I notice that once liveness tracking has been done phisrc
> nodes get annotated with the desired shared register that the phi should
> occupy; suddenly, the phi stuff all makes sense.)

Glad to hear that.


> (PS. Please don't cc me if you're also mailing the list --- I only need
> one copy!)

You mean your email client is not smart enough to realize that is the
same email :-)  I prefer to get CC directly to get a sense of being part of
the discussion. My email will filter differently if I am directly addressed.

Chris

Re: Writing compilers, and example.c vs compile-i386.c

[David Given]

[-- Attachment #1: Type: text/plain, Size: 2180 bytes --]

Christopher Li wrote:
[...]
> BTW, you shouldn't take example.c too seriously per Linus' suggestion.

It does show the telltale signs of being hacked together on an
experimental basis, but it's proving invaluable as a source for getting
my own stuff working --- and it *is* working, I can actually generate
more or less correct code! (Assuming you like adding numbers together,
of course.) The register allocation algorithm example.c uses is
extremely noddy but seems to be reasonably effective; as my
'architecture' has a large but finite number of 'registers', all I
really need is something to cause dead registers to be reused, for which
this is perfectly adequate.

(I suspect that bolting on a real register allocator ought to be very
easy given that the code's already in SSA form. Maybe at some stage I'll
have a look, but register allocators really aren't my strong point.)

I do, however, still have a few other queries...

- how do you determine the scalar type of a pseudo?

For example, I haven't found any way yet of distinguishing between an
int and a float. I need to generate different code for these, but there
don't seem to be any relevant fields in pseudo_t. There isn't even
anything in the pseudo's storage structure. The instruction sometimes
has a size field, but these aren't unique. I may need this for other
things than float support; for example, I may need to generate special
pointer arithmetic code.

- if I wish to rewrite a basic block's instruction list --- for example,
to decompose instructions that use a non-register pseudo into two
instructions --- do I need to do anything other than iterate through the
bb's list and insert instruction nodes? Is there any additional
housekeeping to do? Naturally, I'd do this *before* calling
track_pseudo_death()...

- what does expand_symbol() do?

-- 
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
│ "I have always wished for my computer to be as easy to use as my
│ telephone; my wish has come true because I can no longer figure out
│ how to use my telephone." --- Bjarne Stroustrup


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: Writing compilers, and example.c vs compile-i386.c

[Christopher Li]

On Fri, Jun 20, 2008 at 4:46 PM, David Given <dg@cowlark.com> wrote:
> - how do you determine the scalar type of a pseudo?

Depend on the pseudo type. If pseudo from a symbol,
pseudo->sym->ctype has the full type information.

If pseudo is from constant expression, pseduo->def->val
is the constant expression. using expr->ctype to get to the ctype.

If pseudo is from normal instruction result, the target type is
the same as any source type. The special case the OP_CAST
instruction, the type is in insn->cast_type.

I agree we should probability make the ctype into instruction so
make the back end easier.

> - if I wish to rewrite a basic block's instruction list --- for example,
> to decompose instructions that use a non-register pseudo into two
> instructions --- do I need to do anything other than iterate through the
> bb's list and insert instruction nodes? Is there any additional
> housekeeping to do? Naturally, I'd do this *before* calling
> track_pseudo_death()...

If you modify instructions in a existing instruction list. Make sure you
keep the pseudo in SSA form, including proper user list.

If you add basic block, you need to update the parent and child list.

> - what does expand_symbol() do?

Well, it expand symbols. That does help does it?

Sparse parsing have a few stage.

The tokenizer parse the source code and convert it into token list.

Pre-process stage expand the macro and handle include files etc.

Parsing stage consume the token list and parse into AST tree.

Evaluate stage does the type propagation, pointer degenerate etc.

Expand stage is mostly for some fix up. E.g. remove obvious dead code
like "#if 0".
The inline function get expanded in this stage.

Hope that helps.

Chris

Re: Writing compilers, and example.c vs compile-i386.c

[David Given]

Christopher Li wrote:
[...]
> I agree we should probability make the ctype into instruction so
> make the back end easier.

That would be nice; in order to find the type of a pseudo that resulted 
from an instruction, I have to recurse back through *that* instructions' 
operands. This seems rather heavyweight.

In fact, because I need to associate a fair bit of data with each 
pseudo, I then cache the type information in the pseudo's user data 
structure, which for now is stored in an AVL tree keyed of the pseudo's 
address (there is no overkill; there is only 'open fire!' and 
'reload!'). May I put in a request for a user field on every sparse data 
structure, for doing this sort of thing, please?

Which brings me to my next question: while I'm now successfully 
compiling some code, including loops, I'm having trouble with other 
code. In particular, it would appear that now and again a bb will export 
a pseudo using one storage, and another bb will import the same pseudo 
but using a *different* storage. This is making it rather hard for me to 
correctly wire up the interconnects between basic blocks. Currently I'm 
working around this using data stored in my user data structure 
described above, but I suspect there's another thing here I'm not 
getting. What's the recommended strategy here?

(Incidentally, thanks for the help you've been giving me; it's been 
aiding me substantially.)

-- 
David Given
dg@cowlark.com