Re: Help on code generation and register allocation

"Thomas Krause" <>
20 Feb 2006 21:43:52 -0500

          From comp.compilers

Related articles
[4 earlier articles]
Re: Help on code generation and register allocation (Ulrich Hobelmann) (2006-02-12)
Re: Help on code generation and register allocation (Whywhat) (2006-02-14)
Re: Help on code generation and register allocation (Ulrich Hobelmann) (2006-02-14)
Re: Help on code generation and register allocation (2006-02-17)
Re: Help on code generation and register allocation (Ivan Boldyrev) (2006-02-17)
Re: Help on code generation and register allocation (Florian Weimer) (2006-02-17)
Re: Help on code generation and register allocation (Thomas Krause) (2006-02-20)
| List of all articles for this month |

From: "Thomas Krause" <>
Newsgroups: comp.compilers
Date: 20 Feb 2006 21:43:52 -0500
Organization: T-Online
References: 06-02-055 06-02-065
Keywords: code, registers
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
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

Thanks again,
Thomas Krause

"Karsten Nyblad" <> 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.

Post a followup to this message

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