Re: Help on code generation and register allocation

Thomas Krause wrote:
> 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?


I do not know, which intermediate language you are using, and if you
have any way of changing if. The big problem of stack based
intermediate languages is that when compiling an instruction it is not
simple to find out, where the output of the instruction is going to end.
    stack based languages are normally in reverse Polish notation. If you
change the notation into Polish notation, i.e., you example becomes


add
push 1
push 2


then you can easily call a procedure to compile add and let that
procedure call a procedure twice, once for each argument. Both
procedures take arguments that describe were the generated instructions
should leave their result when the instructions are executed.


In practice there is little difference between what you suggest and what
I suggest, but what I suggest may be simpler to understand.


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


Graph coloring is normally preferred when you have many register on the
machine, but x86 has few (assuming that you are not compiling for
AMD64.) I would chose linear scan. In fact, I would chose something
even simpler for a beginning. Writing a very simple code generator
could easily take more than a month full time work. Unless you have
somebody paying you, I would suggest, that you keep it simple. I would
start with simply placing the top of the stack in registers. When there
is no more place in the stack, I would spill the register holding the
lowest element of the stack still in registers.


Karsten Nyblad
d148f3wg02 at sneakemail dot com

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