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

1227.2 TRANSLATION INTO TREES .................................................................................. 124KINDS OF EXPRESSIONS .......................................................................................... 124SIMPLE VARIABLES .................................................................................................. 126ARRAY VARIABLES .................................................................................................. 127STRUCTURED L-VALUES .........................................................................................

128SUBSCRIPTING AND FIELD SELECTION............................................................... 129A SERMON ON SAFETY ............................................................................................ 130ARITHMETIC ............................................................................................................... 130CONDITIONALS ..........................................................................................................

131STRINGS ....................................................................................................................... 132RECORD AND ARRAY CREATION..........................................................................

133WHILE LOOPS ............................................................................................................. 134FOR LOOPS .................................................................................................................. 135FUNCTION CALL ........................................................................................................ 135STATIC LINKS ............................................................................................................. 1367.3 DECLARATIONS ....................................................................................................... 136VARIABLE DEFINITION ............................................................................................

136FUNCTION DEFINITION ............................................................................................ 137FRAGMENTS................................................................................................................ 138CLASSES AND OBJECTS ........................................................................................... 139PROGRAM TRANSLATION TO TREES........................................................................ 139EXERCISES.......................................................................................................................

140Chapter 8: Basic Blocks and Traces....................................................................................... 142OVERVIEW....................................................................................................................... 1428.1 CANONICAL TREES ................................................................................................. 143TRANSFORMATIONS ON ESEQ ............................................................................... 143GENERAL REWRITING RULES ................................................................................ 145MOVING CALLS TO TOP LEVEL .............................................................................

147A LINEAR LIST OF STATEMENTS........................................................................... 1478.2 TAMING CONDITIONAL BRANCHES ................................................................... 148BASIC BLOCKS ........................................................................................................... 148TRACES......................................................................................................................... 149FINISHING UP.............................................................................................................. 150OPTIMAL TRACES......................................................................................................

150FURTHER READING....................................................................................................... 151EXERCISES....................................................................................................................... 151Chapter 9: Instruction Selection.............................................................................................

153OVERVIEW....................................................................................................................... 153TREE PATTERNS......................................................................................................... 153OPTIMAL AND OPTIMUM TILINGS ........................................................................ 1569.1 ALGORITHMS FOR INSTRUCTION SELECTION ................................................

156MAXIMAL MUNCH .................................................................................................... 156DYNAMIC PROGRAMMING ..................................................................................... 158TREE GRAMMARS...................................................................................................... 159FAST MATCHING........................................................................................................ 161EFFICIENCY OF TILING ALGORITHMS .................................................................

1629.2 CISC MACHINES ....................................................................................................... 1629.3 INSTRUCTION SELECTION FOR THE MiniJava COMPILER.............................. 165ABSTRACT ASSEMBLY LANGUAGE INSTRUCTIONS........................................ 165PRODUCING ASSEMBLY INSTRUCTIONS ............................................................

167PROCEDURE CALLS .................................................................................................. 169IF THERE'S NO FRAME POINTER ............................................................................ 1706PROGRAM INSTRUCTION SELECTION...................................................................... 170REGISTER LISTS ......................................................................................................... 171FURTHER READING....................................................................................................... 173EXERCISES.......................................................................................................................

173Chapter 10: Liveness Analysis............................................................................................... 175OVERVIEW....................................................................................................................... 17510.1 SOLUTION OF DATAFLOW EQUATIONS .......................................................... 176CALCULATION OF LIVENESS ................................................................................. 177REPRESENTATION OF SETS..................................................................................... 179TIME COMPLEXITY ...................................................................................................

179LEAST FIXED POINTS................................................................................................ 180STATIC VS. DYNAMIC LIVENESS........................................................................... 181INTERFERENCE GRAPHS.......................................................................................... 18210.2 LIVENESS IN THE MiniJava COMPILER .............................................................. 183GRAPHS ........................................................................................................................

183CONTROL-FLOW GRAPHS........................................................................................ 184LIVENESS ANALYSIS ................................................................................................ 185PROGRAM CONSTRUCTING FLOW GRAPHS ........................................................... 186PROGRAM LIVENESS .................................................................................................... 186EXERCISES.......................................................................................................................