Lectures

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.


22.05.97: Compiler Organization

A summary of how a compiler is organized, including an example of competent but non-optimizing code generation for a reduced-instruction set computer. Establishes the environment in which an optimizer works, and illustrates the kinds of inefficiencies an optimizer might address.

05.06.97: Values

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.

12.06.97: Code Motion

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.

19.06.97: Data Flow Analysis

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.

26.06.97: Combining Analyses

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.

03.07.97: Global Register Allocation

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 allocation decisions. These techniques are only applicable to architectures that provide a significant number of registers with identical characteristics.
William.Waite@Colorado.edu
Revision $Revision: 1.5 $