Re: Help on code generation and register allocation

Thank you all for your help!


I cannot change the intermediate language, so I have to deal with reverse
Polish notation.


I think I will take your idea and build a very simple codegenerator first,
without much optimation. After that I can slowly improve the code
generation. Graph coloring or linear scan seems to complicated to begin
with...


Thanks again,
Thomas Krause


"Karsten Nyblad" <d148f3wg02@sneakemail.com> wrote:
>> 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.

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