A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 4

186Chapter 11: Register Allocation............................................................................................. 188OVERVIEW....................................................................................................................... 18811.1 COLORING BY SIMPLIFICATION........................................................................ 188EXAMPLE ..................................................................................................................... 18911.2 COALESCING...........................................................................................................

191SPILLING ...................................................................................................................... 19311.3 PRECOLORED NODES ........................................................................................... 194TEMPORARY COPIES OF MACHINE REGISTERS ................................................ 194CALLER-SAVE AND CALLEE-SAVE REGISTERS ................................................

195EXAMPLE WITH PRECOLORED NODES ................................................................ 19511.4 GRAPH-COLORING IMPLEMENTATION............................................................ 198DATA STRUCTURES .................................................................................................. 199INVARIANTS ...............................................................................................................

200PROGRAM CODE ........................................................................................................ 20011.5 REGISTER ALLOCATION FOR TREES ................................................................ 205PROGRAM GRAPH COLORING.................................................................................... 207ADVANCED PROJECT: SPILLING............................................................................ 208ADVANCED PROJECT: COALESCING .................................................................... 208FURTHER READING....................................................................................................... 208EXERCISES.......................................................................................................................

208Chapter 12: Putting It All Together........................................................................................ 211OVERVIEW....................................................................................................................... 211PROGRAM PROCEDURE ENTRY/EXIT....................................................................... 212PROGRAM MAKING IT WORK.....................................................................................

213Programming projects .................................................................................................... 213Part Two: Advanced Topics................................................................................................... 215Chapter List ........................................................................................................................ 215Chapter 13: Garbage Collection............................................................................................. 216OVERVIEW....................................................................................................................... 21613.1 MARK-AND-SWEEP COLLECTION ..................................................................... 21713.2 REFERENCE COUNTS ............................................................................................ 22013.3 COPYING COLLECTION ........................................................................................

22113.4 GENERATIONAL COLLECTION........................................................................... 225713.5 INCREMENTAL COLLECTION ............................................................................. 22713.6 BAKER'S ALGORITHM .......................................................................................... 22913.7 INTERFACE TO THE COMPILER.......................................................................... 230FAST ALLOCATION ...................................................................................................

230DESCRIBING DATA LAYOUTS ................................................................................ 231DERIVED POINTERS .................................................................................................. 231PROGRAM DESCRIPTORS ............................................................................................ 232PROGRAM GARBAGE COLLECTION.......................................................................... 233FURTHER READING.......................................................................................................

233EXERCISES....................................................................................................................... 234Chapter 14: Object-Oriented Languages................................................................................ 236OVERVIEW....................................................................................................................... 23614.1 CLASS EXTENSION ................................................................................................ 23614.2 SINGLE INHERITANCE OF DATA FIELDS ......................................................... 237METHODS.....................................................................................................................

23714.3 MULTIPLE INHERITANCE .................................................................................... 23814.4 TESTING CLASS MEMBERSHIP........................................................................... 24014.5 PRIVATE FIELDS AND METHODS ...................................................................... 24314.6 CLASSLESS LANGUAGES..................................................................................... 24314.7 OPTIMIZING OBJECT-ORIENTED PROGRAMS................................................. 244PROGRAM MiniJava WITH CLASS EXTENSION........................................................ 245FURTHER READING.......................................................................................................

245EXERCISES....................................................................................................................... 245Appendix A: MiniJava Language Reference Manual ............................................................ 247A.1 LEXICAL ISSUES......................................................................................................

247A.2 GRAMMAR................................................................................................................ 247A.3 SAMPLE PROGRAM ................................................................................................ 2488PrefaceThis book is intended as a textbook for a one- or two-semester course in compilers.

Studentswill see the theory behind different components of a compiler, the programming techniquesused to put the theory into practice, and the interfaces used to modularize the compiler. Tomake the interfaces and programming examples clear and concrete, we have written them inJava. Another edition of this book is available that uses the ML language.Implementation project The "student project compiler" that we have out-lined is reasonablysimple, but is organized to demonstrate some important techniques that are now in commonuse: abstract syntax trees to avoid tangling syntax and semantics, separation of instructionselection from register allocation, copy propagation to give flexibility to earlier phases of thecompiler, and containment of target-machine dependencies.

Unlike many "student compilers"found in other textbooks, this one has a simple but sophisticated back end, allowing goodregister allocation to be done after instruction selection.This second edition of the book has a redesigned project compiler: It uses a subset of Java,called MiniJava, as the source language for the compiler project, it explains the use of theparser generators JavaCC and SableCC, and it promotes programming with the Visitorpattern. Students using this edition can implement a compiler for a language they're familiarwith, using standard tools, in a more object-oriented style.Each chapter in Part I has a programming exercise corresponding to one module of acompiler.

Software useful for the exercises can be found athttp://uk.cambridge.org/resources/052182060X (outside North America);http://us.cambridge.org/titles/052182060X.html (within North America).Exercises Each chapter has pencil-and-paper exercises; those marked with a star are morechallenging, two-star problems are difficult but solvable, and the occasional three-starexercises are not known to have a solution.Course sequence The figure shows how the chapters depend on each other.9•••A one-semester course could cover all of Part I (Chapters 1-12), with studentsimplementing the project compiler (perhaps working in groups); in addition, lecturescould cover selected topics from Part II.An advanced or graduate course could cover Part II, as well as additional topics fromthe current literature. Many of the Part II chapters can stand independently from Part I,so that an advanced course could be taught to students who have used a different bookfor their first course.In a two-quarter sequence, the first quarter could cover Chapters 1-8, and the secondquarter could cover Chapters 9-12 and some chapters from Part II.Acknowledgments Many people have provided constructive criticism or helped us in otherways on this book.