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 Java^TM® 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.
Author(s): Andrew W. Appel
Edition: 2
Year: 2002
Language: English
Pages: 512
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
