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

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

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

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.

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

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:
[...]

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

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.

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.

Glad to hear that.

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

Christopher Li wrote:
[...]

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

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 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.

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

Christopher Li wrote:
[...]

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
[email protected]