Contents

Compiler design for stack machines, in particular register allocation, is an under researched area. In this thesis I present a framework for analysing and developing register allocation techniques for stack machines. Using this framework, I analyse previous register allocation methods and develop two new algorithms for global register allocation, both of which outperform previous algorithms, and lay the groundwork for future enhancements. Finally I discuss how effective global register allocation for stack machines can influence the design of high performance stack architectures. Included with this thesis is a portable C compiler for stack machines, which incorporates these new register allocation methods. The C compiler and as-sociated tools (assembler, linker and simulator) are included in the CD. Acknowledgements This work was done as part of the UFO project, to develop a soft-core stack processor utilising the latest research on stack based architectures. Its ai