|[4 earlier articles]|
|Re: Help on code generation and register allocation email@example.com (Ulrich Hobelmann) (2006-02-12)|
|Re: Help on code generation and register allocation firstname.lastname@example.org (Whywhat) (2006-02-14)|
|Re: Help on code generation and register allocation email@example.com (Ulrich Hobelmann) (2006-02-14)|
|Re: Help on code generation and register allocation firstname.lastname@example.org (2006-02-17)|
|Re: Help on code generation and register allocation email@example.com (Ivan Boldyrev) (2006-02-17)|
|Re: Help on code generation and register allocation firstname.lastname@example.org (Florian Weimer) (2006-02-17)|
|Re: Help on code generation and register allocation Forum.Thomas.Krause@gmx.de (Thomas Krause) (2006-02-20)|
|From:||"Thomas Krause" <Forum.Thomas.Krause@gmx.de>|
|Date:||20 Feb 2006 21:43:52 -0500|
|Posted-Date:||20 Feb 2006 21:43:52 EST|
Thank you all for your help!
I cannot change the intermediate language, so I have to deal with reverse
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
"Karsten Nyblad" <email@example.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
>> 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
>> 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
> 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
>> for register allocations so far: graph coloring (slow to compile, but
>> 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
> 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
Search the comp.compilers archives again.