Help on code generation and register allocation

Hello,


I need help writing my compiler. The front end stuff (parsing, etc.)
is not the problem, but the back end is.


1.) My idea is to first build a forrest of expression trees for the
parsed code, then map the nodes of the tree to the registers of my
target architecture (X86) and then produce the code. But as simple as
its sounds I don't know really how I should do that.


Building the expression trees should not be too hard: The source language is
a stack based intermediate language and I could use a "virtual stack" to
keep track of all the operands and where they come from and then simply
connect them to the operation. For example:
push 1
push 2
add


would result in a tree where the "add" operation is the root and 1 and
2 are the leafs (operands).


Or is there a better/easier way to do this?


2.) The next problem is the register allocation. I looked at two algorithms
for register allocations so far: graph coloring (slow to compile, but good
results) and linear scan (faster to compile, but not so optimized). The
problem is that I don't fully understand a.) the theory behind that
(especial the graph theory stuff) and b.) how to implement it in real code.


My mathematical background is not good enough to understand the
theories and I did not found anything on the web that explains this
stuff in a way that an average programmer can understand. Do you know
where I can find good tutorials, etc. on this topic?


3.) The actual code generation should not be too hard after that (?). It
should be enough to walk the tree from bottom to top and emit the matching
x86 instructions, right?


So basically what I need help with, is everything after creating my
expression tree.


Just for the record:
- My x86 asm experience is not great, but should be enough for this job
- Although I have enough experience in C/C++, I want to write this compiler
in C# and I prefer a clean (object oriented) solution over a faster one
- As I already mentioned the source code is a stack based intermediate
language and the target should be x86


Any help is appreciated and sorry for my bad englisch!


Thanks a lot,
Thomas Krause


P.S. I ordered the book Modern Compiler Design by Dick Grune yesterday. Do
you have any comments on this book, or do you know any other good book that
could help me?

Return to the comp.compilers page.
Search the comp.compilers archives again.