ClassXInteractive Lecture Streaming

Pr. Lam introduces the Class to CS243, and presents motives behind studying compilers. Gradiance link can be put here for each whole lecture.

Dataflow analysis is introduced using reaching definitions and live variables as examples

Semi-lattice is described to provide a theoretical background for reasoning about the correctness, precision, and convergence properties of data flow analysis.

Constant propagation is described as an example of non-distributive data flow analysis. Loops are defined in graph-theoretical terms.

Partial redundancy elimination (PRE) is an analysis that subsumes multiple analyses including common subexpression elimination and loop invariant code motion. PRE is also a good example that shows how...

The last two passes (minimizing register pressure and cleaning up) are described. A register allocation algorithm based on graph coloring is described.

Instruction scheduling is introduced in this lecture, including basic block scheduling and global scheduling. An algorithm for basic global scheduling is discussed.

Software pipelining is introduced in this lecture, along with the problem formulation, an example, and algorithm.

Introduction to Pointer Analysis (interprocedural, flow-insensitive) and Datalog.

Introduction to Binary Decision Diagram and the comparison between BDD and Datalog, followed by the BDD algorithm and the discussion of its performance.

Introduction to Basic Parallelization, Data Dependence Analysis, and Interprocedural Parallelization.

Discussions about Parallelism and Locality, and their Loop Transformations: Blocking and Affine Partitioning.

Introduction to memory management and garbage collection.

Discussions about Incremental Garbage Collection and Partial Garbage Collection.

Static and Dynamic Program Analysis: Synergies and Applications (guest lecture by Mayur Naik from Intel Labs, Berkeley).