Previous |

- GRAMMAR 1.3: A straight-line coding language.
- PROGRAM 1.5: Representation of straight-line programs.

- PROGRAM 2.9: JavaCC specification of the tokens from Image 2.2.
- PROGRAM 2.10: SableCC specification of the tokens from Image 2.2.

- GRAMMAR 3.1: A syntax for straight-line programs.
- DERIVATION 3.2
- GRAMMAR 3.5
- GRAMMAR 3.8
- GRAMMAR 3.10
- GRAMMAR 3.11
- GRAMMAR 3.12
- ALGORITHM 3.13: Iterative computation of
*FIRST, FOLLOW*, and*nullable*. - GRAMMAR 3.15
- GRAMMAR 3.20
- GRAMMAR 3.23
- GRAMMAR 3.26: A grammar capturing the essence of expressions, variables, and pointer-dereference (by the
`*`) operator in the C language. - GRAMMAR 3.30
- GRAMMAR 3.31: JavaCC version of Grammar 3.30.
- GRAMMAR 3.32: SableCC version of Grammar 3.30.
- GRAMMAR 3.34: SableCC productions of Grammar 3.32 with conflicts resolved.
- GRAMMAR 3.37: Yacc grammar with precedence directives.
- GRAMMAR 3.38: Yacc grammar with precedence directives.

- PROGRAM 4.1: Recursive-descent interpreter for part of Grammar 3.15.
- PROGRAM 4.2: JavaCC version of a variant of Grammar 3.15.
- GRAMMAR 4.3: Abstract syntax of expressions.
- PROGRAM 4.4: Building syntax trees for expressions.
- PROGRAM 4.5: Exp class for Program 4.4.
- PROGRAM 4.7: Syntax classes with accept methods.
- PROGRAM 4.8: An interpreter visitor.
- PROGRAM 4.10: MiniJava visitor

- PROGRAM 5.2: Hash table with external chaining.
- PROGRAM 5.5: The interface of package
`Symbol`. - PROGRAM 5.6: Symbol table implementation.
- PROGRAM 5.8: A
`visit`method for variable declarations - PROGRAM 5.9: A
`visit`method for plus expressions

- PROGRAM 6.1: An example of higher-order functions.
- PROGRAM 6.3: Nested functions.

- PROGRAM 7.3: The
`Cx`class. - PROGRAM 7.5: A MiniJava program.

- ALGORITHM 8.2: Generation of traces.

- PROGRAM 9.3: Maximal Munch in Java.
- PROGRAM 9.5:
`Assem`-instructions for`munchStm`. - PROGRAM 9.6:
`Assem`-instructions for`munchExp`. - PROGRAM 9.7: The
`Codegen`class.

- GRAPH 10.1: Control-flow graph of a program.
- EQUATIONS 10.3: Dataflow equations for liveness analysis.
- ALGORITHM 10.4: Computation of liveness by iteration.
- GRAPH 10.8: Standard static dataflow analysis will not take advantage of the fact that node 4 can never be reached.
- PROGRAM 10.10: The
`Graph`abstract data type.

- GRAPH 11.1: Interference graph for a program. Dotted lines are not interference edges but indicate move instructions.
- GRAPH 11.2: After removal of
`h`,`g`,`k`. - GRAPH 11.5: (a) after coalescing
`c`and`d`; (b) after coalescing`b`and`j`. - PROGRAM 11.8: A C function and its translation into instructions
- ALGORITHM 11.9: Simple register allocation on trees.
- ALGORITHM 11.10: Sethi-Ullman labeling algorithm.
- ALGORITHM 11.11: Sethi-Ullman register allocation for trees.

- PROGRAM 12.1: Package
`Frame`.

- ALGORITHM 13.2: Depth-first search.
- ALGORITHM 13.3: Mark-and-sweep garbage collection.
- ALGORITHM 13.5: Depth-first search using an explicit stack.
- ALGORITHM 13.6: Depth-first search using pointer reversal.
- ALGORITHM 13.8: Forwarding a pointer.
- ALGORITHM 13.9: Breadth-first copying garbage collection.
- ALGORITHM 13.11: Semi-depth-first forwarding.
- ALGORITHM 13.13: Basic tricolor marking

- PROGRAM 14.1: An object-oriented program.

- PROGRAM 15.1: A FunJava program.
- PROGRAM 15.3: Binary search trees implemented in two ways.
- PROGRAM 15.4: Built-in types and functions for PureFunJava.
- PROGRAM 15.5: PureFunJava program to read
*i*, print*i*!. - PROGRAM 15.6:
`printTable`in PureFunJava. - PROGRAM 15.7: Java implementation of
`printTable`. - ALGORITHM 15.8: Inline expansion of function bodies. We assume that no two declarations declare the same name.
- ALGORITHM 15.9: Loop-preheader transformation.
- ALGORITHM 15.10: Loop-invariant hoisting.
- PROGRAM 15.11:
`printTable`as automatically specialized. - PROGRAM 15.12:
`printTable`after closure conversion (class constructors omitted). - PROGRAM 15.14: Call-by-name transformation applied to Program 15.3a.
- PROGRAM 15.15: Summing the squares.
- PROGRAM 15.16: Partial call-by-name using the results of strictness analysis; compare with Program 15.14.
- ALGORITHM 15.17: First-order strictness analysis.

- ALGORITHM 16.1: Checking wellformedness of types and subtyping.
- ALGORITHM 16.2: Field and method search.
- ALGORITHM 16.3: Type-checking expressions. Expressions with integer type are omitted, because they are checked just as in MiniJava
- ALGORITHM 16.4: Type-checking class declarations.

- PROGRAM 17.3
- ALGORITHM 17.5: Topological sort by depth-first search.
- ALGORITHM 17.6: A work-list algorithm for reaching definitions.
- ALGORITHM 17.7: Value numbering.
- PROGRAM 17.9:
`p`and`q`are not aliases.

- PROGRAM 18.8: A loop before and after induction-variable optimizations.
- PROGRAM 18.10: Useless loop unrolling.
- PROGRAM 18.11: Useful loop unrolling; (a) works correctly only for an even number of iterations of the original loop; (b) works for any number of iterations of the original loop.

- ALGORITHM 19.6: Inserting φ-functions.
- ALGORITHM 19.7: Renaming variables.
- ALGORITHM 19.9: Lengauer-Tarjan algorithm for computing dominators.
- ALGORITHM 19.10: Two versions of AncestorWithLowestSemi and Link functions for operations on spanning forest. The naive version (a) takes
*O*(*N*) per operation (so the algorithm runs in time*O*(*N*^{2})) and the efficient version (b) takes*O*(log*N*) amortized time per operation, for an*O*(*N*log*N*) algorithm. - ALGORITHM 19.12: Dead-code elimination in SSA form.
- ALGORITHM 19.17: Calculation of live ranges in SSA form, and building the inter-ference graph. The graph-walking algorithm is expressed as a mutual recursion between
*LiveOutAtBlock*,*LiveInAtStatement*, and*LiveOutAtStatement*. The recursion is bounded whenever*LiveOutAtBlock*finds an already walked block, or whenever*LiveOutAtStatement*reaches the definition of*v*. - PROGRAM 19.19: SSA program of Image 19.4g converted to functional intermediate form.
- ALGORITHM 19.20: Translating SSA to functional intermediate form.

- PROGRAM 20.4: (a) A
**for**-loop to be software-pipelined. (b) After a scalar-replacement optimization (in the deFlnition of*a*); and scalar variables labeled with their iteration-number. - GRAPH 20.5: Data-dependence graph for Program 20.4b: (a) original graph, in which solid edges are same-iteration dependences and dotted edges are loop-carried dependences; (b) acyclic dependences of the unrolled loop.
- ALGORITHM 20.9: Iterative modulo scheduling.

- PROGRAM 21.6: Inserting prefetches using loop unrolling or nested loops.