CS 426

Compiler structure, syntax analysis, syntax-directed translation, automatically constructed recognizers, semantic analysis, code generation, intermediate language, optimization techniques. Course Information: 3 undergraduate hours. 3 or 4 graduate hours. Prerequisite: Credit or concurrent enrollment in CS 421.

1. Engineering a Compiler by Cooper and Torczon, published by Morgan Kaufman.

2. Compilers - Principles, Techniques, and Tools (2nd Edition) by Aho, Lam, Sethi, and Ullman, published by Addison-Wesley.

Choose the appropriate compiler internal representation for different kinds of compiler tasks. (1, 2, 6)
Translate a source-level language into a low-level compiler internal representation. (1, 2, 6)
Analyze the major control flow properties of a program, including control flow graphs, dominators, natural loops, and reducible vs. irreducible flow graphs. (1, 2, 6)
Identify the classical optimizations that could be applicable to a given piece of code to improve its performance. (1, 2, 6)
Construct and solve the dataflow equations for a given dataflow problem. (1, 2, 6)
Identify the dataflow problem(s) required for a given dataflow optimization. (1, 2, 6)
Describe the algorithms and design tradeoffs for back-end ("native") code generation for a modern superscalar processor (1, 2, 6)
Implement the major phases of a simple compiler, including scanning, parsing, intermediate code generation, and a few program optimizations. (1, 2, 3, 6)

Introduction to compilers and program optimization
Compiler internal representations.
Run-time environments supporting compiler-generated code.
Translation from source-level programming languages to low-level intermediate code
Control flow graphs, dominators, natural loops, and reducibility
Terminology, classification, correctness and profitability of program optimizations
Classical local and peephole program optimizations
Classical global program optimizations
Dataflow analysis and the iterative dataflow algorithm
Back-end ("native") code generation
Global register allocation

Revisions in last 6 years	Approximately when revision was done	Reason for revision	Data or documentation available?
Dropped in-class coverage of parsing techniques while retaining the programming project to implement a scanner and parser using automated tools.	Fall 2008	Many students take the prerequisite course, CS 421, here at U. Illinois, and parsing is covered adequately in that class. The time saved is being used for more important topics, especially Program Optimization.	No. The change was based on coverage in CS 421 and on informal feedback from students.
Simplified two major parts of the programming project.	Fall 2008	Revised the workload in two components of the course project to eliminate an incidental but long (and tedious) part of the learning curve so that students could focus more time and effort on the parts that gave practice with the new concepts taught in the class.	No. The change was based on the experience with the longer and more tedious version in the previous year.

Elective.

3/14/2019by Vikram Adve