Anyone concerned with code generation wil want to take a look at this book. While the methodology is presented in the context of the Production Quality Compiler-Compiler (PQCC) project at Carnegie-Mellon, the ideas are independent of that project. The reader will have a problem sorting out the general principles from the unnecessarily complex and PQCC-specific discourse. But the effort will be worthwhile for those keenly interested in this area, as Leverett discusses a wealth of topics.
The approach to register allocation taken here is similar to that of the Bliss-11 [1] and PL.8 [2,3] compilers; that is, initial code is generated assuming an infinite number of registers. Later, these virtual registers are mapped to real registers and storage locations. Both Leverett and the PL.8 project use Yershov’s ideas [4, 5] of coloring an interference graph to obtain the assignment of virtual to real registers. Leveratt gives a good theoretical discussion of the problem.
The PQCC system operates in three phases, like the Bliss-11 compiler: preliminary code selection, virtual to real register assignment, and actual code generation. This addresses the “fundamental phase ordering problem involving register alocation and code selection, in that either can produce more nearly optimal results if the other has already run.”
This book is a repackaging of the author’s 1981 CMU PhD thesis. The thesis is reprinted without any recognizable changes other than that the original footnotes have become endnotes. These are awkward to find when reading and not worth the effort; I hope UMI Research Press will use footnotes in the future. An Appendix brings the thesis six months further up to date. Even though the author points out that the Appendix was written as a separate paper, I would have preferred to see its contents edited into the main body of the book.