List of Examples

Introduction

A straight-line coding language.
Representation of straight-line programs.

Lexical Analysis

JavaCC specification of the tokens from Image 2.2.
SableCC specification of the tokens from Image 2.2.

Parsing

A syntax for straight-line programs.
Iterative computation of FIRST, FOLLOW, and nullable.
A grammar capturing the essence of expressions, variables, and pointer-dereference (by the *) operator in the C language.
JavaCC version of Grammar 3.30.
SableCC version of Grammar 3.30.
SableCC productions of Grammar 3.32 with conflicts resolved.
Yacc grammar with precedence directives.
Yacc grammar with precedence directives.

Abstract Syntax

Recursive-descent interpreter for part of Grammar 3.15.
JavaCC version of a variant of Grammar 3.15.
Abstract syntax of expressions.
Building syntax trees for expressions.
Exp class for Program 4.4.
Syntax classes with accept methods.
An interpreter visitor.
MiniJava visitor

Semantic Analysis

Hash table with external chaining.
The interface of package Symbol.
Symbol table implementation.
A visit method for variable declarations
A visit method for plus expressions

Activation Records

An example of higher-order functions.
Nested functions.

Translation to Intermediate Code

The Cx class.
A MiniJava program.

Basic Blocks and Traces

Generation of traces.

Instruction Selection

Maximal Munch in Java.
Assem-instructions for munchStm.
Assem-instructions for munchExp.
The Codegen class.

Liveness Analysis

Control-flow graph of a program.
Dataflow equations for liveness analysis.
Computation of liveness by iteration.
Standard static dataflow analysis will not take advantage of the fact that node 4 can never be reached.
The Graph abstract data type.

Register Allocation

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

Putting It All Together

Package Frame.

Garbage Collection

Depth-first search.
Mark-and-sweep garbage collection.
Depth-first search using an explicit stack.
Depth-first search using pointer reversal.
Forwarding a pointer.
Breadth-first copying garbage collection.
Semi-depth-first forwarding.
Basic tricolor marking

Object-Oriented Languages

An object-oriented program.

Functional Programming Languages

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

Polymorphic Types

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

Dataflow Analysis

Topological sort by depth-first search.
A work-list algorithm for reaching definitions.
Value numbering.
p and q are not aliases.

Loop Optimizations

A loop before and after induction-variable optimizations.
Useless loop unrolling.
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

Inserting φ-functions.
Renaming variables.
Lengauer-Tarjan algorithm for computing dominators.
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.
Dead-code elimination in SSA form.
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.
SSA program of Image 19.4g converted to functional intermediate form.
Translating SSA to functional intermediate form.

Pipelining and Scheduling

(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.
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.
Iterative modulo scheduling.

The Memory Hierarchy

Inserting prefetches using loop unrolling or nested loops.

MiniJava Language Reference Manual