List of Examples
Introduction
- GRAMMAR 1.3: A straight-line coding language.
- PROGRAM 1.5: Representation of straight-line programs.
Lexical Analysis
- PROGRAM 2.9: JavaCC specification of the tokens from Image 2.2.
- PROGRAM 2.10: SableCC specification of the tokens from Image 2.2.
Parsing
- 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.
Abstract Syntax
- 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
Semantic Analysis
- 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
Activation Records
- PROGRAM 6.1: An example of higher-order functions.
- PROGRAM 6.3: Nested functions.
Translation to Intermediate Code
- PROGRAM 7.3: The Cx class.
- PROGRAM 7.5: A MiniJava program.
Basic Blocks and Traces
- ALGORITHM 8.2: Generation of traces.
Instruction Selection
- 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.
Liveness Analysis
- 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.
Register Allocation
- 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.
Putting It All Together
- PROGRAM 12.1: Package Frame.
Garbage Collection
- 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
Object-Oriented Languages
- PROGRAM 14.1: An object-oriented program.
Functional Programming Languages
- 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.
Polymorphic Types
- 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.
Dataflow Analysis
- 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.
Loop Optimizations
- 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.
Static Single-Assignment Form
- 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(N2)) 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.
Pipelining and Scheduling
- 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.
The Memory Hierarchy
- PROGRAM 21.6: Inserting prefetches using loop unrolling or nested loops.
Appendix A: MiniJava Language Reference Manual
