skip to main content

CS 426 - Compiler Construction

Fall 2020

TitleRubricSectionCRNTypeHoursTimesDaysLocationInstructor
Compiler ConstructionCS426N343355ONL31230 - 1345 T R    Lawrence Rauchwerger
Compiler ConstructionCS426N443356ONL41230 - 1345 T R    Lawrence Rauchwerger

Documents

Official Description

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: CS 421.

Course Director

Text(s)

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.

Learning Goals

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)

Topic List

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

Assessment and Revisions

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.

Required, Elective, or Selected Elective

Elective.

Last updated

3/14/2019by Vikram Adve