The notes for each lecture summarize the topics covered in that lecture and
give pointers to the literature.
They do not constitute a complete treatment of the topics, nor do they
reflect everything that was said in class.
A summary of how a compiler is organized, including an example of
competent but non-optimizing code generation for a reduced-instruction set
Establishes the environment in which an optimizer works, and illustrates
the kinds of inefficiencies an optimizer might address.
Explains how to characterize a program in terms of the values it computes.
Shows how redundant computations arise from constructs over which the
programmer has no control.
Defines different kinds of regions within a program, settling on the
complete procedure as the region of interest.
Introduces the static single-assignment form of the program,
shows how to construct it,
and illustrates the removal of common subexpressions.
Introduces the concept of redundancy in time, and shows how this redundancy
can be reduced by moving computations within the program.
Describes constraints on such movements, and considers the effect of code
motion on the number of registers required by a program.
Determines optimum placements of computations on the basis of both code
size and register usage.
Introduces predicates on which the compiler can base code motion decisions.
Uses the computation of these predicates to illustrate a general model for
inferring information about specific program points.
Shows how the general model can be used to propagate constants and to
determine whether code can be executed.
Explains how to combine data flow analyses in cases where the inferences
being made are mutually dependent.
Carries two examples through the entire process:
formulating the problem according to the general model,
specifying the components,
and carrying out the computation.
Shows how to exploit the large number of registers provided by RISC
machines to reduce execution time by improving access to operands.
Models the register allocation problem as a graph coloring problem, and
explains how machine characteristics are used to guide heuristics for
These techniques are only applicable to architectures that provide a
significant number of registers with identical characteristics.