Modern Compiler Implementation in Java, 2Ed

This textbook describes all phases of a compiler: lexical analysis, parsing, abstract syntax, semantic actions, intermediate representations, instruction selection via tree matching, dataflow analysis, graph-coloring register allocation, and runtime systems. It includes thorough coverage of current techniques in code generation and register allocation, and the compilation of functional and object-oriented languages. The most accepted and successful techniques are described and illustrated with actual JavaTM® classes. The first part is suitable for a one-semester first course in compiler design. The second part; which includes the compilation of object-oriented and functional languages, garbage collection, loop optimization, SSA form, instruction scheduling, and optimization for cache-memory hierarchies; can be used for a second-semester or graduate course. This new edition includes more discussion of Java and object-oriented programming concepts such as visitor patterns plus a new Mini-Java programming project. A unique feature is the newly redesigned compiler project in Java for a subset of Java itself. The project includes both front-end and back-end phases. Cover......Page 1 Half-title......Page 3 Title......Page 5 Copyright......Page 6 Contents......Page 7 Preface......Page 11 PART ONE Fundamentals of Compilation......Page 13 1 Introduction......Page 15 1.1 MODULES AND INTERFACES......Page 16 1.2 TOOLS AND SOFTWARE......Page 17 1.3 DATA STRUCTURES FOR TREE LANGUAGES......Page 19 STRAIGHT-LINE PROGRAM INTERPRETER......Page 23 EXERCISES......Page 26 2 Lexical Analysis......Page 28 2.1 LEXICAL TOKENS......Page 29 2.2 REGULAR EXPRESSIONS......Page 30 2.3 FINITE AUTOMATA......Page 33 RECOGNIZING THE LONGEST MATCH......Page 35 2.4 NONDETERMINISTIC FINITE AUTOMATA......Page 36 CONVERTING A REGULAR EXPRESSION TO AN NFA......Page 37 CONVERTING AN NFA TO A DFA......Page 39 2.5 LEXICAL-ANALYZER GENERATORS......Page 42 JAVACC......Page 43 SABLECC......Page 44 FURTHER READING......Page 45 EXERCISES......Page 46 3 Parsing......Page 50 3.1 CONTEXT-FREE GRAMMARS......Page 52 DERIVATIONS......Page 53 AMBIGUOUS GRAMMARS......Page 54 3.2 PREDICTIVE PARSING......Page 57 FIRST AND FOLLOW SETS......Page 59 CONSTRUCTING A PREDICTIVE PARSER......Page 62 ELIMINATING LEFT RECURSION......Page 63 ERROR RECOVERY......Page 65 3.3 LR PARSING......Page 67 LR PARSING ENGINE......Page 68 LR(0) PARSER GENERATION......Page 70 SLR PARSER GENERATION......Page 74 LR(1) ITEMS; LR(1) PARSING TABLE......Page 75 LALR(1) PARSING TABLES......Page 76 HIERARCHY OF GRAMMAR CLASSES......Page 78 LR PARSING OF AMBIGUOUS GRAMMARS......Page 79 JAVACC......Page 80 SABLECC......Page 82 PRECEDENCE DIRECTIVES......Page 84 SYNTAX VERSUS SEMANTICS......Page 87 3.5 ERROR RECOVERY......Page 88 RECOVERY USING THE ERROR SYMBOL......Page 89 GLOBAL ERROR REPAIR......Page 90 FURTHER READING......Page 93 EXERCISES......Page 94 RECURSIVE DESCENT......Page 98 4.2 ABSTRACT PARSE TREES......Page 101 POSITIONS......Page 103 4.3 VISITORS......Page 105 ABSTRACT SYNTAX FOR MiniJava......Page 110 EXERCISES......Page 113 5.1 SYMBOL TABLES......Page 115 MULTIPLE SYMBOL TABLES......Page 117 EFFICIENT IMPERATIVE SYMBOL TABLES......Page 118 EFFICIENT FUNCTIONAL SYMBOL TABLES......Page 119 SYMBOLS......Page 120 5.2 TYPE-CHECKING MiniJava......Page 123 EXERCISES......Page 126 6 Activation Records......Page 128 HIGHER-ORDER FUNCTIONS......Page 129 6.1 STACK FRAMES......Page 130 REGISTERS......Page 132 PARAMETER PASSING......Page 133 FRAME-RESIDENT VARIABLES......Page 135 STATIC LINKS......Page 136 6.2 FRAMES IN THE MiniJava COMPILER......Page 138 REPRESENTATION OF FRAME DESCRIPTIONS......Page 140 LOCAL VARIABLES......Page 141 MANAGING STATIC LINKS......Page 143 FURTHER READING......Page 144 EXERCISES......Page 145 7 Translation to Intermediate Code......Page 148 7.1 INTERMEDIATE REPRESENTATION TREES......Page 149 KINDS OF EXPRESSIONS......Page 152 SIMPLE VARIABLES......Page 155 ARRAY VARIABLES......Page 156 STRUCTURED L-VALUES......Page 157 SUBSCRIPTING AND FIELD SELECTION......Page 158 A SERMON ON SAFETY......Page 159 ARITHMETIC......Page 160 CONDITIONALS......Page 161 STRINGS......Page 162 RECORD AND ARRAY CREATION......Page 163 WHILE LOOPS......Page 165 FUNCTION CALL......Page 166 VARIABLE DEFINITION......Page 167 FUNCTION DEFINITION......Page 168 FRAGMENTS......Page 169 CLASSES AND OBJECTS......Page 170 TRANSLATION TO TREES......Page 171 EXERCISES......Page 172 8 Basic Blocks and Traces......Page 174 8.1 CANONICAL TREES......Page 175 TRANSFORMATIONS ON ESEQ......Page 176 GENERAL REWRITING RULES......Page 178 MOVING CALLS TO TOP LEVEL......Page 180 8.2 TAMING CONDITIONAL BRANCHES......Page 181 BASIC BLOCKS......Page 182 TRACES......Page 183 FINISHING UP......Page 184 FURTHER READING......Page 185 EXERCISES......Page 186 TREE PATTERNS......Page 188 9.1 ALGORITHMS FOR INSTRUCTION SELECTION......Page 191 MAXIMAL MUNCH......Page 192 DYNAMIC PROGRAMMING......Page 194 TREE GRAMMARS......Page 195 EFFICIENCY OF TILING ALGORITHMS......Page 198 9.2 CISC MACHINES......Page 199 9.3 INSTRUCTION SELECTION FOR THE MiniJava COMPILER......Page 202 ABSTRACT ASSEMBLY LANGUAGE INSTRUCTIONS......Page 203 PRODUCING ASSEMBLY INSTRUCTIONS......Page 205 PROCEDURE CALLS......Page 206 INSTRUCTION SELECTION......Page 209 REGISTER LISTS......Page 210 FURTHER READING......Page 212 EXERCISES......Page 213 10 Liveness Analysis......Page 215 CALCULATION OF LIVENESS......Page 217 TIME COMPLEXITY......Page 220 LEAST FIXED POINTS......Page 221 STATIC VS. DYNAMIC LIVENESS......Page 222 INTERFERENCE GRAPHS......Page 224 GRAPHS......Page 226 CONTROL-FLOW GRAPHS......Page 227 LIVENESS ANALYSIS......Page 228 LIVENESS......Page 229 EXERCISES......Page 230 11 Register Allocation......Page 231 11.1 COLORING BY SIMPLIFICATION......Page 232 EXAMPLE......Page 233 11.2 COALESCING......Page 235 SPILLING......Page 238 TEMPORARY COPIES OF MACHINE REGISTERS......Page 239 EXAMPLE WITH PRECOLORED NODES......Page 240 11.4 GRAPH-COLORING IMPLEMENTATION......Page 244 DATA STRUCTURES......Page 245 INVARIANTS......Page 246 PROGRAM CODE......Page 247 11.5 REGISTER ALLOCATION FOR TREES......Page 253 GRAPH COLORING......Page 256 FURTHER READING......Page 257 EXERCISES......Page 258 12 Putting It All Together......Page 261 PROCEDURE ENTRY/EXIT......Page 262 Programming projects......Page 264 PART TWO Advanced Topics......Page 267 13.1 MARK-AND-SWEEP COLLECTION......Page 269 13.2 REFERENCE COUNTS......Page 274 13.3 COPYING COLLECTION......Page 276 13.4 GENERATIONAL COLLECTION......Page 281 13.5 INCREMENTAL COLLECTION......Page 284 13.6 BAKER’S ALGORITHM......Page 286 FAST ALLOCATION......Page 287 DESCRIBING DATA LAYOUTS......Page 288 DERIVED POINTERS......Page 289 DESCRIPTORS......Page 290 FURTHER READING......Page 291 EXERCISES......Page 293 14.1 CLASS EXTENSION......Page 295 14.2 SINGLE INHERITANCE OF DATA FIELDS......Page 296 METHODS......Page 297 14.3 MULTIPLE INHERITANCE......Page 298 14.4 TESTING CLASS MEMBERSHIP......Page 301 14.5 PRIVATE FIELDS AND METHODS......Page 304 14.7 OPTIMIZING OBJECT-ORIENTED PROGRAMS......Page 305 FURTHER READING......Page 307 EXERCISES......Page 308 15 Functional Programming Languages......Page 310 15.1 A SIMPLE FUNCTIONAL LANGUAGE......Page 311 15.2 CLOSURES......Page 313 15.3 IMMUTABLE VARIABLES......Page 314 CONTINUATION-BASED I/O......Page 316 OPTIMIZATION OF PURE FUNCTIONAL LANGUAGES......Page 318 15.4 INLINE EXPANSION......Page 320 15.5 CLOSURE CONVERSION......Page 328 15.6 EFFICIENT TAIL RECURSION......Page 331 15.7 LAZY EVALUATION......Page 333 CALL-BY-NAME EVALUATION......Page 334 CALL-BY-NEED......Page 335 EVALUATION OF A LAZY PROGRAM......Page 336 OPTIMIZATION OF LAZY FUNCTIONAL PROGRAMS......Page 337 STRICTNESS ANALYSIS......Page 340 FURTHER READING......Page 343 EXERCISES......Page 345 16 Polymorphic Types......Page 347 16.1 PARAMETRIC POLYMORPHISM......Page 348 16.2 POLYMORPHIC TYPE-CHECKING......Page 351 16.3 TRANSLATION OF POLYMORPHIC PROGRAMS......Page 356 16.4 RESOLUTION OF STATIC OVERLOADING......Page 359 FURTHER READING......Page 360 EXERCISES......Page 361 NO MAGIC BULLET......Page 362 17.1 INTERMEDIATE REPRESENTATION FOR FLOW ANALYSIS......Page 363 QUADRUPLES......Page 364 REACHING DEFINITIONS......Page 366 AVAILABLE EXPRESSIONS......Page 368 LIVENESS ANALYSIS......Page 370 COPY PROPAGATION......Page 371 17.4 SPEEDING UP DATAFLOW ANALYSIS......Page 372 BASIC BLOCKS......Page 373 ORDERING THE NODES......Page 374 WORK-LIST ALGORITHMS......Page 375 INCREMENTAL DATAFLOW ANALYSIS......Page 376 17.5 ALIAS ANALYSIS......Page 381 ALIAS ANALYSIS BASED ON TYPES......Page 382 ALIAS ANALYSIS BASED ON FLOW......Page 383 USING MAY-ALIAS INFORMATION......Page 385 EXERCISES......Page 386 REDUCIBLE FLOW GRAPHS......Page 388 ALGORITHM FOR FINDING DOMINATORS......Page 391 IMMEDIATE DOMINATORS......Page 392 LOOPS......Page 393 LOOP PREHEADER......Page 394 HOISTING......Page 396 18.3 INDUCTION VARIABLES......Page 397 DETECTION OF INDUCTION VARIABLES......Page 399 STRENGTH REDUCTION......Page 400 ELIMINATION......Page 401 REWRITING COMPARISONS......Page 402 18.4 ARRAY-BOUNDS CHECKS......Page 403 18.5 LOOP UNROLLING......Page 407 FURTHER READING......Page 408 EXERCISES......Page 409 19 Static Single-Assignment Form......Page 411 CRITERIA FOR INSERTING Ø-FUNCTIONS......Page 414 THE DOMINANCE FRONTIER......Page 416 INSERTING Ø-FUNCTIONS......Page 418 EDGE SPLITTING......Page 420 DEPTH-FIRST SPANNING TREES......Page 422 SEMIDOMINATORS......Page 424 THE LENGAUER-TARJAN ALGORITHM......Page 425 DEAD-CODE ELIMINATION......Page 429 SIMPLE CONSTANT PROPAGATION......Page 430 CONDITIONAL CONSTANT PROPAGATION......Page 431 PRESERVING THE DOMINANCE PROPERTY......Page 434 19.4 ARRAYS, POINTERS, AND MEMORY......Page 435 MEMORY DEPENDENCE......Page 436 19.5 THE CONTROL-DEPENDENCE GRAPH......Page 437 AGGRESSIVE DEAD-CODE ELIMINATION......Page 438 19.6 CONVERTING BACK FROM SSA FORM......Page 440 LIVENESS ANALYSIS FOR SSA......Page 441 19.7 A FUNCTIONAL INTERMEDIATE FORM......Page 442 FURTHER READING......Page 446 EXERCISES......Page 448 20 Pipelining and Scheduling......Page 452 20.1 LOOP SCHEDULING WITHOUT RESOURCE BOUNDS......Page 456 MODULO SCHEDULING......Page 460 FINDING THE MINIMUM INITIATION INTERVAL......Page 463 OTHER CONTROL FLOW......Page 466 SHOULD THE COMPILER SCHEDULE INSTRUCTIONS?......Page 467 20.3 BRANCH PREDICTION......Page 468 STATIC BRANCH PREDICTION......Page 469 SHOULD THE COMPILER PREDICT BRANCHES?......Page 470 FURTHER READING......Page 471 EXERCISES......Page 472 21 The Memory Hierarchy......Page 476 21.1 CACHE ORGANIZATION......Page 477 21.2 CACHE-BLOCK ALIGNMENT......Page 480 ALIGNMENT IN THE INSTRUCTION CACHE......Page 481 21.3 PREFETCHING......Page 482 21.4 LOOP INTERCHANGE......Page 488 21.5 BLOCKING......Page 489 21.6 GARBAGE COLLECTION & THE MEMORY HIERARCHY......Page 492 FURTHER READING......Page 493 EXERCISES......Page 494 A.2 GRAMMAR......Page 496 A.3 SAMPLE PROGRAM......Page 498 Bibliography......Page 499 Index......Page 507 This textbook describes all phases of a modern compiler, including current techniques in code generation and register allocation, for imperative, functional and object-oriented languages. In a concise and practical way the author describes the fundamentals of compilation and then moves on to advanced topics such as SSA form, loop scheduling, and optimization for cache-memory hierarchies. The new edition features a redesigned compiler project in Java, for a subset of Java itself, covering both front-end and back-end phases "The first part of the book, Fundamentals of Compilation, is suitable for a one-semester first course in compiler design. The second part, Advanced Topics, which includes the compilation of object-oriented and functional languages, garbage collection, loop optimization, SSA form, instruction scheduling, optimization for cache-memory hierarchies, can be used for a second-semester or graduate course."--Jacket