Re: Help on code generation and register allocation

Whywhat wrote:
> Very good book indeed is so called Dragon book by Sethi, Aho and
> Ullman:``Compilers Principles, Techniques and Tools''. It's good for
> beginners and has a lot of information on almost every topic connected
> with compilers. As for Modern Compiler Design - I guess that it is for
> more advanced readers though I don't know really as didn't read it.
> Anyway it won't be useless for you, I'm sure.


I remember that when I read that book years ago, I felt distracted by
too many unnecessary implementation details, like how to write a
symbol table in C and stuff like that. However it's been a while, and
back then I was busy understanding the parsing stages. Does the
Dragon Book have some good information on register allocation that's
not in the Tiger Book (Andrew Appel's Modern Compiler Implementation
in XY)?


> 2) You can download sources of LLVM system and look for register
> allocation implementations here (LLVM\lib\CodeGen as far as I remember)
> There you'll find improved linear scan algo - so called iterative scan.
> Remember that x86 doesn't have enough registers to satisfy your program
> needs (I guess, no architecture has enough registers ;)) So some of
> your variables will be stored in memory (e.g. on local stack; it's
> called spilling). But, of course, they should be loaded on register
> when performing operations on them. Thus you should either use two
> predefined registers for loading/storing variables from/to memory. Or
> modify your code and rerun the allocation algorithm. The latter is
> harder to implement.


Spilling is probably normal, especially on the Intel. My question:
are there register allocators that do a good job at preparing for tail
calls / tail recursion?


On the Intel that would mean to have a big enough stack frame to save
some registers there (to have some in the first place :D), to assemble
function arguments in the low area of the stack frame, to restore
registers from the high area, and then to pop the stack frame down to
the function arguments. Then, Jump! I'm wondering if it's better to
have an algorithm do that, or maybe just extend the function's body to
include some extra code to prepare for tail calling, and have the
"usual" compiler compile that.
--
Suffering from Gates-induced brain leakage...
[The dragon book is now about 30 years old, so old that it predates
the widespread use of x86 chips for PCs. There's a new edition in the
works but it's chronically a few months away from publication. -John]

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